結果
問題 | No.5020 Averaging |
ユーザー | butsurizuki |
提出日時 | 2024-02-20 16:45:24 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 4 ms / 1,000 ms |
コード長 | 3,724 bytes |
コンパイル時間 | 3,258 ms |
コンパイル使用メモリ | 264,392 KB |
実行使用メモリ | 6,676 KB |
スコア | 25,316,232 |
最終ジャッジ日時 | 2024-02-25 12:46:04 |
合計ジャッジ時間 | 5,107 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,676 KB |
testcase_01 | AC | 3 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 3 ms
6,676 KB |
testcase_04 | AC | 2 ms
6,676 KB |
testcase_05 | AC | 2 ms
6,676 KB |
testcase_06 | AC | 4 ms
6,676 KB |
testcase_07 | AC | 3 ms
6,676 KB |
testcase_08 | AC | 3 ms
6,676 KB |
testcase_09 | AC | 3 ms
6,676 KB |
testcase_10 | AC | 2 ms
6,676 KB |
testcase_11 | AC | 4 ms
6,676 KB |
testcase_12 | AC | 3 ms
6,676 KB |
testcase_13 | AC | 3 ms
6,676 KB |
testcase_14 | AC | 3 ms
6,676 KB |
testcase_15 | AC | 3 ms
6,676 KB |
testcase_16 | AC | 3 ms
6,676 KB |
testcase_17 | AC | 2 ms
6,676 KB |
testcase_18 | AC | 2 ms
6,676 KB |
testcase_19 | AC | 3 ms
6,676 KB |
testcase_20 | AC | 3 ms
6,676 KB |
testcase_21 | AC | 3 ms
6,676 KB |
testcase_22 | AC | 4 ms
6,676 KB |
testcase_23 | AC | 3 ms
6,676 KB |
testcase_24 | AC | 2 ms
6,676 KB |
testcase_25 | AC | 4 ms
6,676 KB |
testcase_26 | AC | 2 ms
6,676 KB |
testcase_27 | AC | 3 ms
6,676 KB |
testcase_28 | AC | 2 ms
6,676 KB |
testcase_29 | AC | 3 ms
6,676 KB |
testcase_30 | AC | 2 ms
6,676 KB |
testcase_31 | AC | 3 ms
6,676 KB |
testcase_32 | AC | 3 ms
6,676 KB |
testcase_33 | AC | 2 ms
6,676 KB |
testcase_34 | AC | 3 ms
6,676 KB |
testcase_35 | AC | 4 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 | 2 ms
6,676 KB |
testcase_40 | AC | 2 ms
6,676 KB |
testcase_41 | AC | 3 ms
6,676 KB |
testcase_42 | AC | 2 ms
6,676 KB |
testcase_43 | AC | 3 ms
6,676 KB |
testcase_44 | AC | 3 ms
6,676 KB |
testcase_45 | AC | 2 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 |
ソースコード
#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]; } } 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; for(int att=0;att<1;att++){ vector<p128> cp=p; vector<int> cres; vector<int> trash(n,0); trash[0]=1; for(int hd=0;hd<50;hd++){ vector<int> lis; for(int i=1;i<n;i++){ if(trash[i]){continue;} // cerr << hd << " " << i << "\n"; vector<p128> up=cp; shrink(i,up); vector<p128> up2; for(int j=1;j<n;j++){ if(trash[j]){continue;} up2.push_back(up[j]); } vector<p128> ch=convex_hull(up2); if(jud(ch)){lis.push_back(i);} } if(lis.empty()){break;} int tg=xor128()%lis.size(); cres.push_back(lis[tg]); shrink(lis[tg],cp); vector<p128> cp2; for(int j=1;j<n;j++){ if(trash[j]){continue;} cp2.push_back(cp[j]); } vector<p128> ch=convex_hull(cp2); for(auto &nx : ch){ long long ox=nx.first; long long oy=nx.second; } trash[lis[tg]]=1; } reverse(cres.begin(),cres.end()); res=cres; } 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; }