結果
問題 |
No.96 圏外です。
|
ユーザー |
|
提出日時 | 2025-07-01 04:51:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 114 ms / 5,000 ms |
コード長 | 5,149 bytes |
コンパイル時間 | 2,609 ms |
コンパイル使用メモリ | 225,488 KB |
実行使用メモリ | 13,568 KB |
最終ジャッジ日時 | 2025-07-01 04:51:42 |
合計ジャッジ時間 | 6,076 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> struct Point{ public: T x,y; Point() : x(0),y(0) {} Point(T a,T b) : x(a),y(b) {} Point &operator=(const Point &b) = default; Point operator+(const Point &b){return Point(x+b.x,y+b.y);} Point operator-(const Point &b){return Point(x-b.x,y-b.y);} Point operator+=(const Point &b){return *this=*this+b;} Point operator-=(const Point &b){return *this=*this-b;} bool operator==(const Point &b){return x==b.x && y==b.y;} bool operator!=(const Point &b){return x!=b.x || y!=b.y;} bool operator<(const Point &b){ if(x == b.x) return y < b.y; else return x < b.x; } bool operator<=(const Point &b){return (*this) < b || (*this) == b;} bool operator>(const Point &b){return !((*this) <= b);} bool operator>=(const Point &b){return !((*this) < b);} friend T inner(const Point a,const Point b){return a.x*b.x+a.y*b.y;} friend T cross(const Point a,const Point b){return a.x*b.y-a.y*b.x;} friend T twodist(const Point a,const Point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}//2乗で返す. }; template<typename T> istream &operator>>(istream &is,Point<T> &a){ is >> a.x >> a.y; return is; } template<typename T> ostream &operator<<(ostream &os,Point<T> &a){ os << a.x << " " << a.y; return os; } template<typename T> vector<Point<T>> Convexhull(vector<Point<T>> &P){ //(x,y)が最小の点から時計回りに頂点を返す. //(xi,yi)と(xi+1,yi+1)は辺になる |P|=1の時注意. sort(P.begin(),P.end()); P.erase(unique(P.begin(),P.end()),P.end()); if(P.size() == 0) return {}; if(P.size() == 1) return {P.at(0),P.at(0)}; vector<Point<T>> A,B; for(auto &p1 : P){ while(A.size() >= 2){ auto &p2 = A.at(A.size()-1); auto &p3 = A.at(A.size()-2); T check = cross(p2-p1,p3-p2); if(check <= 0) A.pop_back(); else break; } A.push_back(p1); } for(auto &p1 : P){ while(B.size() >= 2){ auto &p2 = B.at(B.size()-1); auto &p3 = B.at(B.size()-2); T check = cross(p2-p1,p3-p2); if(check >= 0) B.pop_back(); else break; } B.push_back(p1); } for(int i=B.size()-2; i>=0; i--) A.push_back(B.at(i)); return A; } class UnionFind{ private: vector<int> par,siz; public: UnionFind(int N){ par.resize(N,-1); siz.resize(N,1); } int root(int x){ //連結成分の代表頂点を返す. if(par.at(x) == -1) return x; else return par.at(x) = root(par.at(x)); } bool unite(int u, int v){ //u,vを連結する 連結してた->false,した->trueを返す. u = root(u),v = root(v); if(u == v) return false; if(siz.at(u) < siz.at(v)) swap(u,v); //Union by size. par.at(v) = u; siz.at(u) += siz.at(v); return true; } bool issame(int u, int v){ //同じ連結成分ならtrue. if(root(u) == root(v)) return true; else return false; } int size(int pos){return siz.at(root(pos));} //posの連結成分の大きさを返す. }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; if(N == 0){cout << 1 << endl; return 0;} vector<Point<int>> P(N); for(auto &p : P) cin >> p,p.x += 10000,p.y += 10000; map<pair<int,int>,int> M; const int n = 20000; vector<vector<pair<int,int>>> Xs(n+1); for(int i=0; i<N; i++) Xs.at(P.at(i).x).push_back({P.at(i).y,i}); for(auto &x : Xs) sort(x.begin(),x.end()); vector<int> OK(11); for(int i=0; i<=10; i++){ for(int k=0; ; k++){ int diff = i*i+k*k; if(diff <= 100) OK.at(i) = k; else break; } } UnionFind Z(N); for(int i=0; i<N; i++){ auto [x,y] = P.at(i); for(int dx=0; dx<=10; dx++,x++){ if(x > 20000) break; int ly = y-OK.at(dx),ry = y+OK.at(dx); auto &X = Xs.at(x); int pos = lower_bound(X.begin(),X.end(),pair{ly,-1})-X.begin(); while(pos < X.size() && X.at(pos).first <= ry) Z.unite(i,X.at(pos).second),pos++; } } vector<vector<int>> G(N); for(int i=0; i<N; i++) G.at(Z.root(i)).push_back(i); double answer = 2; for(auto &g : G){ if(g.size() <= 1) continue; vector<Point<int>> now; for(auto &p : g) now.push_back(P.at(p)); auto con = Convexhull(now); con.pop_back(); int pos = 0,n = con.size(); for(int i=0; i<n; i++){ while(true){ int one = twodist(con.at(i),con.at(pos)),two = twodist(con.at(i),con.at((pos+1)%n)); if(one < two){ answer = max(answer,sqrt(two)+2); pos++; if(pos == n) pos = 0; } else{answer = max(answer,sqrt(one)+2); break;} } } } cout << fixed << setprecision(20) << answer << endl; }