結果

問題 No.96 圏外です。
コンテスト
ユーザー koyumeishi
提出日時 2014-12-09 04:50:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 739 ms / 5,000 ms
コード長 8,738 bytes
コンパイル時間 1,709 ms
コンパイル使用メモリ 114,356 KB
実行使用メモリ 24,696 KB
最終ジャッジ日時 2024-12-24 08:01:59
合計ジャッジ時間 8,346 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>

using namespace std;

#define EPS 1e-6

class xy{
	
public:
	double x;
	double y;

	xy(){

	}
	
	xy(double xx, double yy){
		x = xx;
		y = yy;
	}

	xy(const xy &v){
		x = v.x;
		y = v.y;
	}

	xy& operator=(const xy &v){
		x = v.x;
		y = v.y;
		return *this;
	}

	xy operator+(const xy &v) const{
		return xy(this->x+v.x, this->y+v.y);
		
	}
	
	xy operator-(const xy &v) const{
		return xy(this->x-v.x, this->y-v.y);
	}
	
	void operator+=(const xy &v){
		x+=v.x;
		y+=v.y;
	}
	void operator-=(const xy &v){
		x-=v.x;
		y-=v.y;
	}
/* something wrong this operator for sorting
	bool operator<(const xy &v){
		if(x!=v.x) return x < v.x;
		return y < v.y;
	}
	bool operator>(const xy &v){
		if(x!=v.x) return x > v.x;
		return y > v.y;
	}
*/

};
//for sorting
bool comp_xy(const xy &a, const xy &b){
	if(a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

//u,v : vector O = (0,0)
double cross(const xy &u, const xy &v){
	return u.x*v.y - u.y*v.x;
}

//u,v : vector O = (0,0)
double dot(const xy &u, const xy &v){
	return u.x*v.x + u.y*v.y;
}

//distance between two points
double dist_p_p(const xy &a, const xy &b){
	return sqrt( fabs(dot(a-b, a-b)) );
}

//distance between a point and a line segment
double dist_p_ls(const xy &p, const xy &s1, const xy &s2){
	xy vl = s2 - s1;
	xy vp = p - s1;

	return fabs( cross(vl, vp) / sqrt( dot(vl, vl) ) );
}

//zero -> p1
int ccw(xy p1, xy p2, xy p3){
	p2 -= p1;
	p3 -= p1;
	double c = cross(p2,p3);
	if( c > EPS /* c > 0 */) return +1;			//counter-clockwise
	if( c < -EPS /* c < 0 */) return -1;		//clock-wise
	if( dot(p2,p3) < -EPS) return +2;			//on segment : p3-p1-p2
	if( dot(p3,p3) < dot(p2,p2) +EPS ) return -2;	//on segment : p1-p3-p2
	return 0;
}

//segment p1-p2, p3-p4
bool inter_ss(xy p1, xy p2, xy p3, xy p4){
	return ( (ccw(p1,p2, p3) * ccw(p1,p2, p4) <= 0) && (ccw(p3,p4, p1) * ccw(p3,p4, p2) <= 0 ) ) ;
}

//convex_hull
vector<xy> convex_hull(vector<xy> &v){
	sort( v.begin(), v.end(), comp_xy );
	int k = 0;	//nums of vertex
	vector<xy> tmp(v.size()*2);
	//conect i from k
	for(int i=0; i<v.size(); i++){
		while(k>1 && cross (tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--;
		tmp[k] = v[i];
		k++;
	}
	
	for(int i=v.size()-2, t=k; i>=0; i--){
		while(k>t && cross(tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--;
		tmp[k] = v[i];
		k++;
	}

	tmp.resize(k-1);
	return tmp;
}

pair<int, int> farthest_point_pair(vector<xy> &v /* v MUST BE CONVEX HULL*/){
	int n = v.size();
	
	int p = 0;	//the point which has min y
	int q = 0;	//the point which has max y
	for(int i=0; i<n; i++){
		if( v[p].y > v[i].y ) p = i;
		if( v[q].y < v[i].y ) q = i;
	}

	double max_dist = dist_p_p( v[p], v[q] );
	int ret_a = p;
	int ret_b = q;
	
	int s = p;
	int t = q;
	while(1){
		if( cross( v[(s+1)%n]-v[s], v[(t+1)%n] - v[t] ) < 0 ) s = (s+1)%n;
		else t = (t+1)%n;

		if( dist_p_p( v[s], v[t] ) > max_dist ){
			ret_a = s;
			ret_b = t;
			max_dist = dist_p_p( v[s], v[t] );
		}
		
		if( s==p && t==q ) break;
	}
	return make_pair(ret_a, ret_b);
}

class UnionFindTree{
	typedef struct {
		int parent;
		int rank;
	}base_node;
	
	vector<base_node> node;
public:
	UnionFindTree(int n){
		node.resize(n);
		for(int i=0; i<n; i++){
			node[i].parent=i;
			node[i].rank=0;
		}
	}

	int find(int x){
		if(node[x].parent == x) return x;
		else{
			return node[x].parent = find(node[x].parent);
		}
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}

	void unite(int x, int y){
		x = find(node[x].parent);
		y = find(node[y].parent);
		if(x==y) return;
		if(node[x].rank < node[y].rank){
			node[x].parent = y;
		}else if(node[x].rank > node[y].rank){
			node[y].parent = x;
		}else{
			node[x].rank++;
			unite(x,y);
		}
	}
};

template <class T> class kd_tree{
	//node[i] covers left<= x <= right, bottom <= y <= right
	vector<T> left;
	vector<T> right;
	vector<T> top;
	vector<T> bottom;

	//number of nodes
	int n;

	//root of kd-tree
	int root;
	
	//node infomation < <x,y>, node number >
	vector<pair<pair<T,T>, int> > node;

	//node[i] covers node[j] such that cover[i].first <= j <= cover[i].second
	vector<pair<int,int> > cover;

	//node[i]'s child nodes. if child[i].first == -1 or child[i].second == -1 then node[i]'s left/right child is empty
	vector<pair<int,int> > child;
	
	//node[i] is divided by x axis then true, else false
	vector<bool> divided_by_x;

	//if x == true then this range [begin,end] will be divided by x axis, else by y axis
	int divide(bool x, int begin, int end){
		//out of range
		if(begin > end || begin < 0 || end >= n){
			return -1;
		}
		T l,r,t,b;
		if(x){
			b = node[begin].first.second;
			t = node[end].first.second;
		}else{
			l = node[begin].first.first;
			r = node[end].first.first;
		}
		if(begin != end){
			if(x) sort(node.begin()+begin, node.begin()+end+1, kd_tree::comp_x);
			else sort(node.begin()+begin, node.begin()+end+1, kd_tree::comp_y);
		}
		
		int med = (begin+end+1)/2;
		if(x){
			l = node[begin].first.first;
			r = node[end].first.first;
		}else{
			b = node[begin].first.second;
			t = node[end].first.second;
		}
		left[med] = l;
		right[med] = r;
		top[med] = t;
		bottom[med] = b;

		cover[med] = make_pair(begin, end);
		divided_by_x[med] = x;

		child[med].first = child[med].second = -1;

		if(med-1 >= begin) child[med].first = divide(!x, begin, med-1);
		if(med+1 <= end) child[med].second = divide(!x, med+1, end);

		return med;
	}

	//find nodes in l <= x <= r, b <= y <= t
	void range_search(const T &l, const T &r, const T &b, const T &t, vector<int> &res, int pos){
		if(pos<0) return;
		
		//all nodes are out of the range
		if(left[pos] > r || right[pos] < l || bottom[pos] > t || top[pos] < b) return;
		
		//all nodes are in the range
		if(l<= left[pos] && right[pos] <= r && b <= bottom[pos] && top[pos] <= t){
			for(int i=cover[pos].first; i<=cover[pos].second; i++){
				res.push_back(node[i].second);
			}
			return;
		}

		//some nodes are in the range
		T x = node[pos].first.first;
		T y = node[pos].first.second;

		//node[pos] is contained
		if(l<=x && x<=r && b<=y && y<=t) res.push_back(node[pos].second);

		//about pos's child
		range_search(l,r,b,t, res, child[pos].first);
		range_search(l,r,b,t, res, child[pos].second);
	}
	
public:
	
	static bool comp_x(const pair<pair<T,T>, int> &a, const pair<pair<T,T>, int> &b) {
		return a.first.first < b.first.first;
	}
	
	static bool comp_y(const pair<pair<T,T>, int> &a, const pair<pair<T,T>, int> &b) {
		return a.first.second < b.first.second;
	}

	//node infomation < <x,y>, node number >
	kd_tree(vector< pair<pair<T,T>, int> > v){
		node = v;

		n = node.size();
		
		left.resize(n);
		right.resize(n);
		top.resize(n);
		bottom.resize(n);
		
		cover.resize(n);
		child.resize(n);
		divided_by_x.resize(n);
		
		
		sort(node.begin(), node.end(), kd_tree::comp_y);
		root = divide(true, 0, n-1);
	}


	
	void range_search(const T &l, const T &r, const T &b, const T &t, vector<int> &res){
		range_search(l,r,b,t, res, root);
	}
};

bool check(xy &a, xy &b){
	return dist_p_p(a,b) <= 10;
}

int main(){
	int n;
	cin >> n;

	vector<pair<pair<int,int>, int> > v(n);
	vector<xy> q(n);
	for(int i=0; i<n; i++){
		int x,y;
		cin >> x >> y;
		v[i] = make_pair(make_pair(x,y), i);
		
		q[i] = xy(x,y);
	}
	
	UnionFindTree uft(n);

	kd_tree<int> kdt(v);
	for(int i=0; i<n; i++){
		vector<int> candidate;
		int x = v[i].first.first;
		int y = v[i].first.second;
		kdt.range_search(x-10, x+10, y-10, y+10, candidate);
		for(int j=0; j<candidate.size(); j++){
			if(candidate[j] == i) continue;
			if(check(q[i], q[ candidate[j] ])){
				uft.unite(i, candidate[j]);
			}
		}
	}
	
	map<int, vector<xy> > S;
	for(int i=0; i<n; i++){
		int par = uft.find(i);
		if(S.find(par) != S.end()){
			S[par].push_back( q[i] );
		}else{
			S[par] = vector<xy>(0);
			S[par].push_back( q[i] );
		}
	}
	
	double ans = 1.0;
	for(auto itr = S.begin(); itr != S.end(); itr++){
		if(itr->second.size() == 1){
			ans = max(ans, 2.0);
			continue;
		}
		
		vector<xy> hull = convex_hull( itr->second );
		
		
		pair<int,int> d = farthest_point_pair(hull);
		double tmp = dist_p_p( hull[d.first], hull[d.second] ) + 2.0;

		ans = max(ans, tmp);
	}

	printf("%.7f\n", ans);
	return 0;
}
0