結果
問題 | No.5009 Draw A Convex Polygon |
ユーザー | karinohito |
提出日時 | 2022-12-02 00:42:26 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 490 ms / 2,600 ms |
コード長 | 1,187 bytes |
コンパイル時間 | 1,974 ms |
実行使用メモリ | 21,892 KB |
スコア | 100,000 |
平均クエリ数 | 100001.00 |
最終ジャッジ日時 | 2022-12-02 00:42:32 |
合計ジャッジ時間 | 3,571 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll mod=998244353; using vll =vector<ll>; using vvll =vector<vll>; #define rep(i,n) for(int i=0;i<n;i++) ll sqrtz(ll N) { ll L = 0; ll R = sqrt(N)+10000; while (abs(R - L) > 1) { ll mid = (R +L) / 2; if (mid * mid <= N)L = mid; else R = mid; } return L; } int main(){ vector<pair<ll,ll>> P; ll N=1e5/4; ll M=1e8; for(ll x=-M+1;x<0;x++){ if(P.size()==N)break; ll y=-sqrtz(M*M-x*x); if(P.size()<2)P.push_back({x,y}); else{ auto d=P[P.size()-1]; auto dd=P[P.size()-2]; ll ddx=d.first-dd.first; ll ddy=-d.second+dd.second; ll dx=x-d.first; ll dy=-y+d.second; if(ddy*dx>dy*ddx){ P.push_back({x,y}); } } } N=P.size(); for(ll n=N-1;n>=0;n--){ P.push_back({-P[n].first,P[n].second}); } N=P.size(); for(ll n=N-1;n>=0;n--){ P.push_back({P[n].first,-P[n].second}); } cout<<P.size()<<endl;; rep(i,P.size())cout<<P[i].first<<" "<<P[i].second<<endl; }