Submission #69121435

---

Source Code Expand

  #include "atcoder/all"
  //#include "atcoder/modint"
  //#pragma GCC optimize("Ofast")
  #include <bits/stdc++.h>
  #include  <string>
  using namespace std;
  using namespace atcoder;
  #define int long long
    template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
  template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
  //const int MOD =1e9+7;
  //constexpr int MOD =10;
  constexpr int MOD =998244353;
  const long long M1=167772161,M2=469762049,M3=1224736769;
  //const int MOD =31607;
  using mint = static_modint<MOD>;
  //using mint = double;
  //using mint = modint;
  ostream& operator << (ostream& ost, const mint& m){ost << m.val();return ost;}
  istream& operator >> (istream& ost,  mint& m){int a;ost >> a;m=a;return ost;}
  double time_limit = 1.8,start_temp=5.0,end_temp=0.0;
  std::random_device seed_gen;
  std::mt19937 engine(seed_gen());

  signed main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    int n;
    std::chrono::_V2::steady_clock::time_point t0= chrono::steady_clock::now();
    cin >> n;
    int x[n],y[n];
    for(int i=0;i<n;i++)cin >> x[i] >> y[i];
    std::uniform_int_distribution<> dist(0, n-1);
    vector<int>v;
    for(int i=0;i<n;i++)v.push_back(i);
    while(true){
      auto now = chrono::steady_clock::now();
      double elapsed = chrono::duration<double>(now - t0).count();
      if(elapsed>time_limit)break;
      int a=dist(engine);
      map<pair<int,int>,int>mp,mp2;
      for(int i=0;i<n;i++)if(i!=a){
        int dx = x[i]-x[a];
        int dy = y[i]-y[a];
        int g = gcd(abs(dx),abs(dy));
        dx/=g,dy/=g;
        if(dx<0)dx=-dx,dy=-dy;
        else if(dx==0&&dy<0)dy=-dy;
        mp[{dx,dy}]++;
        mp2[{dx,dy}]=i;
      }
      for(auto p:mp)if(p.second+1>n/2){
        cout<<"Yes"<<endl;
        cout<<y[mp2[p.first]]-y[a]<<" "<<x[a]-x[mp2[p.first]]<<' '<<x[mp2[p.first]]*y[a]-x[a]*y[mp2[p.first]]<<endl;
        return 0;
      }

      
    }
    cout<<"No"<<endl;
    

    
  }

Submission Info

Judge Result