結果

問題 No.96 圏外です。
コンテスト
ユーザー KKT89
提出日時 2019-09-02 22:14:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,968 bytes
コンパイル時間 1,809 ms
コンパイル使用メモリ 105,428 KB
実行使用メモリ 209,400 KB
最終ジャッジ日時 2024-12-17 18:50:48
合計ジャッジ時間 142,361 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 23
権限があれば一括ダウンロードができます

ソースコード

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){
			i=di;
		}
		else{
			j=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;
}
0