結果
問題 | No.5009 Draw A Convex Polygon |
ユーザー | harurun |
提出日時 | 2022-11-09 01:29:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,530 ms / 2,600 ms |
コード長 | 2,554 bytes |
コンパイル時間 | 2,059 ms |
実行使用メモリ | 84,404 KB |
スコア | 248,047 |
平均クエリ数 | 248048.00 |
最終ジャッジ日時 | 2022-12-01 23:30:18 |
合計ジャッジ時間 | 5,465 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ソースコード
#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<900){ 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; } } } erase_duplicate(Pol); 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 N=ans.size(); cout<<N<<endl; for(const Point_i &i:ans){ cout<<i.real()<<" "<<i.imag()<<endl; } return 0; }