#include #include #include #include #include #include #include #include #include using namespace std; using ll=long long; template inline void erase_duplicate(vector& A){sort(A.begin(),A.end());A.erase(unique(A.begin(),A.end()),A.end());} using Point_i=complex; 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 convex_hull(vector &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 &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 rr(-MM,MM),eo(0,1); unordered_set pXs,mXs; ll R=1000000000; vector Pol; ll M=10000000; Pol.reserve(M); while(Pol.size()(clock()-start)/CLOCKS_PER_SEC*1000.0<1.8){ 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 C=convex_hull(Pol); ll K=C.size(); vector ans; ans.reserve(K); for(ll i=0;i