結果
問題 | No.5009 Draw A Convex Polygon |
ユーザー | karinohito |
提出日時 | 2022-12-02 01:31:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,759 bytes |
コンパイル時間 | 2,349 ms |
実行使用メモリ | 34,548 KB |
スコア | 0 |
平均クエリ数 | 913840.00 |
最終ジャッジ日時 | 2022-12-02 01:31:38 |
合計ジャッジ時間 | 3,773 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll mod=998244353; using vll =vector<ll>; using vvll =vector<vll>; #define all(A) A.begin(),A.end() #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; } ll gcd(ll(a), ll(b)) { if (a == 0)return b; if (b == 0)return a; ll c = a; while (a % b != 0) { c = a % b; a = b; b = c; } return b; } int main(){ vector<pair<int,int>> P; ll N=1e6/4; vector<pair<double,pair<int,int>>> G; for(ll i=1;i<=1200;i+=2){ for(ll j=i+2;j<=1200;j+=2){ ll g=gcd(i,j); if(g!=1)continue; G.push_back({double(i)/double(j),{i,j}}); G.push_back({double(j)/double(i),{j,i}}); if(G.size()==N)break; } } sort(all(G)); //reverse(all(G)); //cout<<G.size()<<endl; //return 0; P.push_back({-141630070-1,-1}); rep(i,N-1){ ll x=P.back().first; ll y=P.back().second; ll nx=x+G[i].second.first; ll ny=y-G[i].second.second; if(nx>0||ny<-1e9){ cout<<"ERROR"<<endl; return 0; } P.push_back({nx,ny}); } P.resize(N*4); //N=P.size(); for(ll n=0;n<N;n++){ P[N+n]={-P[N-n-1].first,P[N-n-1].second}; P[2*N+n]={-P[n].first,-P[n].second}; P[3*N+n]={P[N-n-1].first,-P[N-n-1].second}; } cout<<P.size()<<endl;; rep(i,P.size())printf("%d %d\n", P[i].first, P[i].second); //rep(i,P.size())cout<<P[i].first<<" "<<P[i].second<<"\n"; return 0; }