結果

問題 No.94 圏外です。(EASY)
ユーザー kyuridenamidakyuridenamida
提出日時 2014-12-08 01:40:27
言語 C++11
(gcc 11.4.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,508 bytes
コンパイル時間 1,447 ms
コンパイル使用メモリ 159,080 KB
実行使用メモリ 99,580 KB
最終ジャッジ日時 2023-09-08 14:18:30
合計ジャッジ時間 9,004 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 AC 38 ms
99,580 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int dfs(int)’:
main.cpp:72:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

ソースコード

diff # 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//と思ったら僕がバカでしたごめんなさいリバーシのルールを忘れていましたごめんなさい
const double INF = 1e12;
const double EPS = 1e-9;
typedef complex<double> P,point;
 
std::istream& operator>>(std::istream& is,P& p)
{
	double x,y;
	is >> x >> y;
	p = P(x,y);
	return is;
}
 
typedef vector<P> G,polygon;
namespace std {bool operator < (const P& a, const P& b) {return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);} }
double cross(const P& a, const P& b) {return imag(conj(a)*b);}
double dot(const P& a, const P& b) {return real(conj(a)*b);}
int ccw(P a, P b, P c) {
	b -= a; c -= a;
	if (cross(b, c) > 0)   return +1;
	if (cross(b, c) < 0)   return -1;
	if (dot(b, c) < 0) return +2;
	if (norm(b) < norm(c)) return -2;
	return 0;
}
vector<point> convex_hull(vector<point> ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  vector<point> ch(2*n);
  for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
    while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
    while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  ch.resize(k-1);
  return ch;
}


vector<int> b[2020][2020];
P ps[120010];

int done[120020];

inline long long dist(P a,P b){
	P c = a-b;
	return c.real() * c.real() + c.imag()*c.imag();
}
vector<P> conv;
int dfs(int id){
	stack<int> S;
	S.push(id);
	while( S.size() ){
		id = S.top(); S.pop();
		if( done[id]++ ) continue;
		P p = ps[id];
		conv.push_back(p);
		int x = (int)p.real()/10;
		int y = (int)p.imag()/10;
		for(int i = -2 ; i <= 2 ; i++){
			for(int j = -2 ; j <= 2 ; j++){
				for( auto next : b[x+i][y+j] ){
					if( dist(ps[next],p) <= 100 ){
						S.push(next);
					}
				}
			}
		}
	}
}
int main(){
	int N;
	cin >> N;
	if( N == 0 ){
		cout << 1.0 << endl;
		return 0;
	}
	for(int i = 0 ; i < N ; i++){
		P p;
		cin >> p;
		p += P(10050,10050);
		ps[i] = p;
		b[(int)p.real()/10][(int)p.imag()/10].push_back(i);
	}
	long long ans = 0;
	for(int i = 0 ; i < N ; i++){
		if( done[i] == 0 ){
			conv.clear();
			dfs(i);
			if( conv.size() >= 3 ){
				conv = convex_hull(conv);
			}
			for( int j = 0 ; j < conv.size() ; j++)
				for(int k = j+1 ; k < conv.size() ; k++)
					ans = max(ans,dist(conv[j],conv[k]));
		}
	}
	printf("%.10lf\n",sqrt(ans)+2);
	
	
}
0