結果
問題 | No.5020 Averaging |
ユーザー | butsurizuki |
提出日時 | 2024-02-21 07:33:18 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 4 ms / 1,000 ms |
コード長 | 4,441 bytes |
コンパイル時間 | 5,104 ms |
コンパイル使用メモリ | 300,152 KB |
実行使用メモリ | 6,676 KB |
スコア | 66,715,047 |
最終ジャッジ日時 | 2024-02-25 12:47:13 |
合計ジャッジ時間 | 6,796 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,676 KB |
testcase_01 | AC | 3 ms
6,676 KB |
testcase_02 | AC | 3 ms
6,676 KB |
testcase_03 | AC | 3 ms
6,676 KB |
testcase_04 | AC | 3 ms
6,676 KB |
testcase_05 | AC | 3 ms
6,676 KB |
testcase_06 | AC | 3 ms
6,676 KB |
testcase_07 | AC | 3 ms
6,676 KB |
testcase_08 | AC | 4 ms
6,676 KB |
testcase_09 | AC | 3 ms
6,676 KB |
testcase_10 | AC | 3 ms
6,676 KB |
testcase_11 | AC | 3 ms
6,676 KB |
testcase_12 | AC | 4 ms
6,676 KB |
testcase_13 | AC | 3 ms
6,676 KB |
testcase_14 | AC | 4 ms
6,676 KB |
testcase_15 | AC | 3 ms
6,676 KB |
testcase_16 | AC | 3 ms
6,676 KB |
testcase_17 | AC | 3 ms
6,676 KB |
testcase_18 | AC | 3 ms
6,676 KB |
testcase_19 | AC | 3 ms
6,676 KB |
testcase_20 | AC | 4 ms
6,676 KB |
testcase_21 | AC | 3 ms
6,676 KB |
testcase_22 | AC | 3 ms
6,676 KB |
testcase_23 | AC | 3 ms
6,676 KB |
testcase_24 | AC | 3 ms
6,676 KB |
testcase_25 | AC | 3 ms
6,676 KB |
testcase_26 | AC | 3 ms
6,676 KB |
testcase_27 | AC | 3 ms
6,676 KB |
testcase_28 | AC | 4 ms
6,676 KB |
testcase_29 | AC | 3 ms
6,676 KB |
testcase_30 | AC | 3 ms
6,676 KB |
testcase_31 | AC | 3 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 | 3 ms
6,676 KB |
testcase_36 | AC | 3 ms
6,676 KB |
testcase_37 | AC | 3 ms
6,676 KB |
testcase_38 | AC | 3 ms
6,676 KB |
testcase_39 | AC | 4 ms
6,676 KB |
testcase_40 | AC | 4 ms
6,676 KB |
testcase_41 | AC | 3 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 | 3 ms
6,676 KB |
testcase_46 | AC | 4 ms
6,676 KB |
testcase_47 | AC | 3 ms
6,676 KB |
testcase_48 | AC | 3 ms
6,676 KB |
testcase_49 | AC | 3 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,bool actsort=true){ // Copyright (c) 2023 0214sh7 // https://github.com/0214sh7/library/ if(P.size()<=2){ return P; } vector<p128> H,L,R; if(actsort){ 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=0;i<p.size();i++){ p[i]=f(p[i],p[tg]); } } using pi=pair<int,int>; vector<pi> gensuf(int remhd,vector<p128> p){ int n=p.size(); vector<int> id(n-1); for(int i=0;i<n-1;i++){ p[i]=p[i+1]; id[i]=i+1; } p.pop_back(); vector<pi> res; for(int hd=0;hd<remhd;hd++){ vector<pair<p128,int>> ppi; for(int i=0;i<p.size();i++){ ppi.push_back({p[i],id[i]}); } sort(ppi.begin(),ppi.end()); for(int i=0;i<p.size();i++){ p[i]=ppi[i].first; id[i]=ppi[i].second; } int tg=-1; i128 gp=1e37; for(int i=0;i<p.size();i++){ vector<p128> up=p; shrink(i,up); vector<p128> htg; for(int j=0;j<p.size();j++){ if(i==j){continue;} htg.push_back(up[j]); } vector<p128> ch=convex_hull(htg,false); 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,p); res.push_back({0,id[tg]}); for(int i=tg;i<p.size();i++){ p[i]=p[i+1]; id[i]=id[i+1]; } p.pop_back(); id.pop_back(); vector<p128> ch=convex_hull(p,false); // cout << hd << " : \n"; // for(auto &nx : ch){ // long long ox=nx.first; // long long oy=nx.second; // cout << ox << " " << oy << "\n"; // }cout << "\n"; } reverse(res.begin(),res.end()); return res; } void simu(vector<pi> &op,vector<p128> &p){ for(auto &nx : op){ p[nx.first]=f(p[nx.first],p[nx.second]); p[nx.second]=p[nx.first]; } } 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<pi> res=gensuf(50,p); cout << res.size() << "\n"; for(auto &nx : res){ cout << nx.first+1 << " " << nx.second+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; }