結果

問題 No.5009 Draw A Convex Polygon
ユーザー harurunharurun
提出日時 2022-11-09 01:55:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,915 ms / 2,600 ms
コード長 2,564 bytes
コンパイル時間 2,142 ms
実行使用メモリ 101,200 KB
スコア 270,223
平均クエリ数 270224.00
最終ジャッジ日時 2022-12-01 23:30:28
合計ジャッジ時間 6,499 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,915 ms
101,200 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <complex>
#include <algorithm>
#include <random>
#include <unordered_set>
#include <stdio.h>
#include <time.h>
#include <math.h>
using namespace std;
using ll=long long;
template<class T> inline void erase_duplicate(vector<T>& A){sort(A.begin(),A.end());A.erase(unique(A.begin(),A.end()),A.end());}

using Point_i=complex<ll>;

namespace std {
  bool operator<(const Point_i &a, const Point_i &b) {
    return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
  }
}

long long cross(const Point_i &a, const Point_i &b) {
  return real(a) * imag(b) - imag(a) * real(b);
}

vector<Point_i> convex_hull(vector<Point_i> &p) {
  int n = (int) p.size(), k = 0;
  if(n <= 2) return p;
  sort(p.begin(), p.end());
  vector< Point_i > ch(2 * n);
  for(int i = 0; i < n; ch[k++] = p[i++]) {
    while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < 0) --k;
  }
  for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {
    while(k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < 0) --k;
  }
  ch.resize(k - 1);
  return ch;
}

inline bool check(const Point_i &a, Point_i b, Point_i c) {
  b = b - a, c = c - a;
  if(cross(b, c) > 0) return true; // 反時計
  return false;                         // other
}

bool is_narrowly_convex(const vector<Point_i> &p) {
  int n = (int) p.size();
  for(int i = 0; i < n; i++) {
    if(!check(p[(i + n - 1) % n], p[i], p[(i + 1) % n])) return false;
  }
  return true;
}


int main(){
  clock_t start=clock();
  const ll MM=1000000000;
  random_device rand;
  mt19937 mt(rand());
  uniform_int_distribution<ll> rr(-MM,MM),eo(0,1);
  unordered_set<ll> pXs,mXs;
  ll R=1000000000;
  vector<Point_i> Pol;
  ll M=10000000;
  Pol.reserve(M);
  while(Pol.size()<M && static_cast<double>(clock()-start)/CLOCKS_PER_SEC*1000.0<1200){
    ll x=rr(mt);
    if(eo(mt)){
      if(pXs.find(x)==pXs.end()){
        pXs.insert(x);
        Pol.push_back(Point_i{x,(ll)ceil(sqrt(R*R-x*x))});
      }else{
        continue;
      }
    }else{
      if(mXs.find(x)==mXs.end()){
        mXs.insert(x);
        Pol.push_back(Point_i{x,-(ll)floor(sqrt(R*R-x*x))});
      }else{
        continue;
      }
    }
  }
  vector<Point_i> C=convex_hull(Pol);
  ll K=C.size();
  vector<Point_i> ans;
  ans.reserve(K);
  for(ll i=0;i<K;i++){
    if(check(C[(i-1+K)%K],C[i],C[(i+1)%K])){
      ans.push_back(C[i]);
    }
  }
  ll Nmax=1000000;
  ll N=ans.size();
  cout<<N<<endl;
  for(ll i=0;i<min(N,Nmax);i++){
    cout<<ans[i].real()<<" "<<ans[i].imag()<<endl;
  }
  return 0;
}
0