結果

問題 No.96 圏外です。
ユーザー KKT89
提出日時 2019-09-03 01:50:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,028 ms / 5,000 ms
コード長 3,970 bytes
コンパイル時間 1,391 ms
コンパイル使用メモリ 105,548 KB
実行使用メモリ 122,692 KB
最終ジャッジ日時 2024-12-21 08:17:32
合計ジャッジ時間 9,741 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <math.h>
#include <complex>
using namespace std;
typedef long long int ll;
typedef complex<long double> Point;
typedef vector<Point> Polygon; // 多角形
const long double eps=1e-9;
namespace std{
    bool operator<(const Point &p,const Point &q){
    if(p.real()<q.real()-eps) return true;
    if(p.real()>q.real()+eps) return false;
    return p.imag()<q.imag();
    }
}
long double dot(Point a,Point b){ // 内積
    return real(conj(a)*b);
}
long double cross(Point a,Point b){ // 外積
    return imag(conj(a)*b);
}
//CCW
int ccw(Point a,Point b,Point c){
    b-=a; c-=a;
    if(cross(b,c)>eps){
        return 1; // a,b,cが反時計回りの順に並ぶ
    }
    if(cross(b,c)<-eps){
        return -1; // a,b,cが時計回りの順に並ぶ
    }
    if(dot(b,c)<0){
        return 2; // c,a,bがこの順に一直線に並ぶ
    }
    if(norm(b)<norm(c)){
        return -2; // a,b,cの順に一直線に並ぶ
    }
    return 0; // a,c,bの順に一直線に並ぶ
}
// 凸包：凸多角形のある一辺上にある点を含まない
Polygon convex_hull(vector<Point> ps){
    int n=(int)ps.size();
    int k=0; // 凸包の頂点数
    sort(ps.begin(),ps.end());
    Polygon qs(2*n); // 構築中の凸包
    for(int i=0;i<n;qs[k++]=ps[i++]){
        while(k>=2&&ccw(qs[k-2],qs[k-1],ps[i])<=0) --k;
    }
    for(int i=n-2,t=k+1;i>=0;qs[k++]=ps[i--]){
        while(k>=t&&ccw(qs[k-2],qs[k-1],ps[i])<=0) --k;
    }
    qs.resize(k-1);
    return qs;
}
// 凸多角形の直径
pair<pair<ll,ll>,long double> convex_diameter(const Polygon& poly){
    int n=(int)poly.size();
    if(n==2){
        return make_pair(make_pair(0,1),abs(poly[0]-poly[1]));
    }
    int i=0,j=0; // ある方向に最も遠い点対
    // x軸方向に最も遠い点対を求める
    for(int k=0;k<n;k++){
        if(poly[k].imag()>poly[i].imag())i=k;
        if(poly[k].imag()<poly[j].imag())j=k;
    }
    pair<ll,ll> resp=make_pair(-1,-1);
    long double resd=0;
    int si,maxi,sj,maxj;
    si=maxi=i; sj=maxj=j;
    while(si!=maxj || sj!=maxi){
        long double cur=abs(poly[si]-poly[sj]);
        if(resd+eps<cur){
            resd=cur;
            resp=make_pair(si,sj);
        }
        int di=(si+1)%n, dj=(sj+1)%n;
        if(cross(poly[di]-poly[si],poly[dj]-poly[sj])<0){
            si=di;
        }
        else{
            sj=dj;
        }
    }
    return make_pair(resp,resd);
}
struct UnionFind{
    vector<int> par,num;
    vector<bool> done;
    UnionFind(int n):par(n),num(n,1),done(n,false){
        iota(par.begin(),par.end(),0);  //include<numeric>
    }
    int find(int v){
        return (par[v]==v)?v:(par[v]=find(par[v]));
    }
    void unite(int u,int v){
        u=find(u),v=find(v);
        if(u==v)return;
        if(num[u]<num[v])swap(u,v);
        num[u]+=num[v];
        par[v]=u;
        done[u]=done[u]|done[v];
    }
    bool same(int u,int v){
        return find(u) == find(v);
    }
    bool ispar(int v){
        return v=find(v);
    }
    int size(int v){
        return num[find(v)];
    }
};
int x[120010],y[120010];
int dx[9]={0,0,0,1,1,1,-1,-1,-1};
int dy[9]={0,1,-1,0,1,-1,0,1,-1};
int main(){
    int n; cin >> n;
    if(n==0){
        cout << 1 << endl;
        return 0;
    }
    Polygon ps;
    vector<vector<vector<ll> > > backet(2010,vector<vector<ll> >(2010));
    for(int i=0;i<n;i++){
        cin >> x[i] >> y[i];
        ps.push_back(Point(x[i],y[i]));
        x[i]+=10000; y[i]+=10000;
        backet[x[i]/10][y[i]/10].push_back(i);
    }
    UnionFind uf(n);
    
    for(int i=0;i<2010;i++){
        for(int j=0;j<2010;j++){
            for(auto v:backet[i][j]){//近接するブロックを探索する
                for(int k=0;k<9;k++){
                    int ni=i+dx[k],nj=j+dy[k];
                    if(ni<0||nj<0)continue;
                    for(auto vv:backet[ni][nj]){
                        if(v==vv)continue;
                        if(abs(ps[v]-ps[vv])<10+eps){
                            uf.unite(v,vv);
                        }
                    }
                }
            }
        }
    }
    vector<Polygon> Polys(n);
    for(int i=0;i<n;i++){
        Polys[uf.find(i)].push_back(ps[i]);
    }
    long double res=0;
    for(int i=0;i<n;i++){
        if(Polys[i].size()<=1)continue;
        Polys[i]=convex_hull(Polys[i]);
        res=max(res,convex_diameter(Polys[i]).second);
    }
    res+=2;
    printf("%.10Lf\n",res);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0