結果
問題 | No.5020 Averaging |
ユーザー | butsurizuki |
提出日時 | 2024-02-20 18:30:46 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 5 ms / 1,000 ms |
コード長 | 4,586 bytes |
コンパイル時間 | 4,565 ms |
コンパイル使用メモリ | 289,496 KB |
実行使用メモリ | 6,676 KB |
スコア | 68,055,930 |
最終ジャッジ日時 | 2024-02-25 12:47:09 |
合計ジャッジ時間 | 6,364 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
6,676 KB |
testcase_01 | AC | 4 ms
6,676 KB |
testcase_02 | AC | 4 ms
6,676 KB |
testcase_03 | AC | 4 ms
6,676 KB |
testcase_04 | AC | 4 ms
6,676 KB |
testcase_05 | AC | 4 ms
6,676 KB |
testcase_06 | AC | 4 ms
6,676 KB |
testcase_07 | AC | 4 ms
6,676 KB |
testcase_08 | AC | 4 ms
6,676 KB |
testcase_09 | AC | 4 ms
6,676 KB |
testcase_10 | AC | 4 ms
6,676 KB |
testcase_11 | AC | 5 ms
6,676 KB |
testcase_12 | AC | 4 ms
6,676 KB |
testcase_13 | AC | 4 ms
6,676 KB |
testcase_14 | AC | 4 ms
6,676 KB |
testcase_15 | AC | 4 ms
6,676 KB |
testcase_16 | AC | 5 ms
6,676 KB |
testcase_17 | AC | 4 ms
6,676 KB |
testcase_18 | AC | 4 ms
6,676 KB |
testcase_19 | AC | 4 ms
6,676 KB |
testcase_20 | AC | 4 ms
6,676 KB |
testcase_21 | AC | 5 ms
6,676 KB |
testcase_22 | AC | 4 ms
6,676 KB |
testcase_23 | AC | 4 ms
6,676 KB |
testcase_24 | AC | 4 ms
6,676 KB |
testcase_25 | AC | 4 ms
6,676 KB |
testcase_26 | AC | 4 ms
6,676 KB |
testcase_27 | AC | 4 ms
6,676 KB |
testcase_28 | AC | 4 ms
6,676 KB |
testcase_29 | AC | 4 ms
6,676 KB |
testcase_30 | AC | 4 ms
6,676 KB |
testcase_31 | AC | 4 ms
6,676 KB |
testcase_32 | AC | 4 ms
6,676 KB |
testcase_33 | AC | 4 ms
6,676 KB |
testcase_34 | AC | 4 ms
6,676 KB |
testcase_35 | AC | 4 ms
6,676 KB |
testcase_36 | AC | 4 ms
6,676 KB |
testcase_37 | AC | 4 ms
6,676 KB |
testcase_38 | AC | 4 ms
6,676 KB |
testcase_39 | AC | 4 ms
6,676 KB |
testcase_40 | AC | 4 ms
6,676 KB |
testcase_41 | AC | 4 ms
6,676 KB |
testcase_42 | AC | 4 ms
6,676 KB |
testcase_43 | AC | 4 ms
6,676 KB |
testcase_44 | AC | 4 ms
6,676 KB |
testcase_45 | AC | 5 ms
6,676 KB |
testcase_46 | AC | 4 ms
6,676 KB |
testcase_47 | AC | 4 ms
6,676 KB |
testcase_48 | AC | 4 ms
6,676 KB |
testcase_49 | AC | 4 ms
6,676 KB |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:140:23: warning: 'y' may be used uninitialized [-Wmaybe-uninitialized] 140 | p128 pp=f(p[x],p[y]); | ^ main.cpp:126:11: note: 'y' was declared here 126 | int x,y; | ^ main.cpp:140:18: warning: 'x' may be used uninitialized [-Wmaybe-uninitialized] 140 | p128 pp=f(p[x],p[y]); | ^ main.cpp:126:9: note: 'x' was declared here 126 | int x,y; | ^
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #include <sys/time.h> using namespace std; long long start_time; void start_clock(){ struct timeval tv; gettimeofday(&tv, NULL); start_time=(tv.tv_sec*1000000+tv.tv_usec); } long long current_clock(){ struct timeval tv; gettimeofday(&tv, NULL); long long current_time=(tv.tv_sec*1000000+tv.tv_usec); // cout << current_time-start_time << "(us)\n"; return current_time-start_time; } unsigned long long xor128(){ static unsigned long long x=123456789,y=362436069,z=521288629,w=88675123; unsigned long long t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } using p128=pair<__int128,__int128>; using i128=__int128; vector<p128> convex_hull(vector<p128> P){ // Copyright (c) 2023 0214sh7 // https://github.com/0214sh7/library/ if(P.size()<=2){ return P; } vector<p128> H,L,R; sort(P.begin(),P.end()); //下半分 for(int i=0;i<P.size();i++){ int j=L.size(); while(j>=2 && (L[j-1].first-L[j-2].first)*(P[i].second-L[j-2].second)<=(L[j-1].second-L[j-2].second)*(P[i].first-L[j-2].first)){ L.pop_back(); j--; } L.push_back(P[i]); } //上半分 for(int i=P.size()-1;i>=0;i--){ int j=H.size(); while(j>=2 && (H[j-1].first-H[j-2].first)*(P[i].second-H[j-2].second)<=(H[j-1].second-H[j-2].second)*(P[i].first-H[j-2].first)){ H.pop_back(); j--; } H.push_back(P[i]); } R=L; for(int i=1;i<H.size()-1;i++){ R.push_back(H[i]); } return R; } p128 f(p128 a,p128 b){ return {(a.first+b.first)/2,(a.second+b.second)/2}; } i128 target=500000000000000000; bool jud(vector<p128> &P){ int n=P.size(); for(int i=0;i<n;i++){ i128 a=P[(i+1)%n].first-P[i].first; i128 b=P[(i+1)%n].second-P[i].second; i128 c=target-P[i].first; i128 d=target-P[i].second; if(a*d-b*c < 0){ return false; } } return true; } void shrink(int tg,vector<p128> &p){ for(int i=1;i<p.size();i++){ p[i]=f(p[i],p[tg]); } } void simu(vector<int> &op,vector<p128> &p){ for(auto &nx : op){ p[0]=f(p[0],p[nx]); p[nx]=p[0]; } } long long eval(p128 x){ return max(x.first-target,x.second-target); } int main(){ start_clock(); ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<p128> p(n); for(int i=0;i<n;i++){ long long x,y; cin >> x >> y; p[i].first=x; p[i].second=y; } vector<pair<int,int>> pfx; for(int tr=0;tr<6;tr++){ int x,y; i128 md=1e37; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(p[i]==p[j]){continue;} p128 pp=f(p[i],p[j]); i128 cd=(pp.first-target)*(pp.first-target)+(pp.second-target)*(pp.second-target); if(md>cd){ md=cd; x=i; y=j; } } } p128 pp=f(p[x],p[y]); p[x]=pp; p[y]=pp; pfx.push_back({x,y}); } // cout << "\n"; // for(auto &nx : p){ // long long ox=nx.first; // long long oy=nx.second; // cout << ox << " " << oy << "\n"; // } vector<int> res; vector<int> trash(n,0); trash[0]=1; vector<p128> cp=p; for(int hd=0;hd<50;hd++){ int tg=-1; i128 gp=1e37; for(int i=1;i<n;i++){ if(trash[i]){continue;} vector<p128> up=cp; shrink(i,up); vector<p128> htg; for(int j=1;j<n;j++){ if(trash[j] || i==j){continue;} htg.push_back(up[j]); } vector<p128> ch=convex_hull(htg); if(jud(ch)){ i128 gx=0,gy=0; for(auto &nx : ch){ gx+=nx.first; gy+=nx.second; } gx/=ch.size(); gy/=ch.size(); i128 gd=(gx-target)*(gx-target)+(gy-target)*(gy-target); if(gp > gd){ gp=gd; tg=i; } } } if(tg==-1){break;} shrink(tg,cp); // cout << hd << " : "; // for(auto &nx : cp){ // long long ox=nx.first; // long long oy=nx.second; // cout << ox << " " << oy << "\n"; // } res.push_back(tg); trash[tg]=1; } reverse(res.begin(),res.end()); cout << pfx.size()+res.size() << "\n"; for(auto &nx : pfx){ cout << nx.first+1 << " " << nx.second+1 << "\n"; } for(auto &nx : res){ cout << 1 << " " << nx+1 << "\n"; } // simu(res,p); // for(auto &nx : p){ // long long ox=nx.first; // long long oy=nx.second; // cout << ox << " " << oy << "\n"; // } return 0; }