結果
問題 | No.5020 Averaging |
ユーザー | butsurizuki |
提出日時 | 2024-02-20 18:24:47 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 5 ms / 1,000 ms |
コード長 | 3,879 bytes |
コンパイル時間 | 4,572 ms |
コンパイル使用メモリ | 284,920 KB |
実行使用メモリ | 6,676 KB |
スコア | 65,151,608 |
最終ジャッジ日時 | 2024-02-25 12:47:06 |
合計ジャッジ時間 | 6,333 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 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 | 5 ms
6,676 KB |
testcase_11 | AC | 4 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 | 4 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 | 4 ms
6,676 KB |
testcase_22 | AC | 4 ms
6,676 KB |
testcase_23 | AC | 4 ms
6,676 KB |
testcase_24 | AC | 5 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 | 5 ms
6,676 KB |
testcase_33 | AC | 5 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 | 5 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 | 5 ms
6,676 KB |
testcase_44 | AC | 4 ms
6,676 KB |
testcase_45 | AC | 4 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 |
ソースコード
#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<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=max((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 << res.size() << "\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; }