結果

問題 No.96 圏外です。
ユーザー koyumeishikoyumeishi
提出日時 2014-12-09 05:15:05
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 247 ms / 5,000 ms
コード長 5,679 bytes
コンパイル時間 1,231 ms
コンパイル使用メモリ 108,800 KB
実行使用メモリ 25,740 KB
最終ジャッジ日時 2024-06-06 15:53:39
合計ジャッジ時間 5,101 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 7 ms
5,376 KB
testcase_06 AC 11 ms
5,376 KB
testcase_07 AC 17 ms
5,392 KB
testcase_08 AC 23 ms
6,164 KB
testcase_09 AC 33 ms
7,108 KB
testcase_10 AC 47 ms
7,948 KB
testcase_11 AC 61 ms
9,864 KB
testcase_12 AC 69 ms
11,948 KB
testcase_13 AC 105 ms
11,780 KB
testcase_14 AC 122 ms
15,376 KB
testcase_15 AC 156 ms
14,916 KB
testcase_16 AC 195 ms
20,172 KB
testcase_17 AC 209 ms
25,740 KB
testcase_18 AC 247 ms
23,400 KB
testcase_19 AC 241 ms
23,532 KB
testcase_20 AC 190 ms
17,256 KB
testcase_21 AC 144 ms
16,128 KB
testcase_22 AC 224 ms
17,780 KB
testcase_23 AC 228 ms
17,748 KB
testcase_24 AC 1 ms
5,376 KB
testcase_25 AC 144 ms
19,264 KB
testcase_26 AC 198 ms
23,792 KB
testcase_27 AC 159 ms
20,880 KB
権限があれば一括ダウンロードができます

ソースコード

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);
		}
	}
};

bool check(xy &a, xy &b){
	return dist_p_p(a,b) <= 10+1e-6;
}

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

	vector<pair<double,int> > events(n*2);
	vector<xy> q(n);
	double k = 1.0/sqrt(2);
	for(int i=0; i<n; i++){
		int x,y;
		cin >> x >> y;

		double xx = k*(x-y);
		double yy = k*(x+y);

		events.push_back( make_pair(xx-10, i) );
		events.push_back( make_pair(xx+10, n+i) );
		
		q[i] = xy(xx,yy);
	}
	sort(events.begin(), events.end());
	
	UnionFindTree uft(n);

	set< pair<double, int> > my_list;
	for(int i=0; i<events.size(); i++){
		int id = events[i].second;
		if(id < n){
			auto begin = my_list.lower_bound( make_pair( q[id].y-11, id) );
			
			auto end = my_list.upper_bound(make_pair( q[id].y+11, id ) );
			
			for(auto itr = begin; itr!=end; itr++){
				if( check(q[id], q[ itr->second ]) ){
					uft.unite(id, itr->second );
				}
			}
			my_list.insert( make_pair( q[id].y, id ) );
		}else{
			my_list.erase( make_pair( q[id-n].y, id-n ) );
		}
	}

	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