結果

問題 No.5020 Averaging
コンテスト
ユーザー butsurizuki
提出日時 2024-02-20 16:45:24
言語 C++23
(gcc 13.3.0 + boost 1.87.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0