結果

問題 No.96 圏外です。
ユーザー kyuridenamidakyuridenamida
提出日時 2014-12-08 01:25:59
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 3,193 bytes
コンパイル時間 1,481 ms
コンパイル使用メモリ 171,228 KB
実行使用メモリ 109,280 KB
最終ジャッジ日時 2024-06-11 18:16:04
合計ジャッジ時間 11,665 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 WA -
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 -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int dfs(int)’:
main.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
   93 | }
      | ^

ソースコード

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);}
struct L : public vector<P> {L(const P &a, const P &b) {push_back(a); push_back(b);} };
struct C {P p; double r;C(const P &p, double r) : p(p), r(r) { } C(){} };
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;
}
 
// Where is Point in Polygon? //
#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]
enum { OUT, ON, IN };
int contains(const polygon& P, const point& p) {
	bool in = false;
	for (int i = 0; i < P.size(); ++i) {
		point a = curr(P,i) - p, b = next(P,i) - p;
		if (imag(a) > imag(b)) swap(a, b);
		if (imag(a) <= 0 && 0 < imag(b))
			if (cross(a, b) < 0) in = !in;
		if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
	}
	return in ? IN : OUT;
}
// Area of Polygon //
double area2(const polygon& P) {
	double A = 0;
	for (int i = 0; i < P.size(); ++i)A += cross(curr(P, i), next(P, i));
	return A;
}
// Totsuhou! Andrew's Monotone Chain //
 
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[2010][2010];
P ps[100010];

int done[100020];

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){
	if( done[id]++ ) return 0;
	P p = ps[id];
	conv.push_back(p);
	int x = (int)p.real()/10;
	int y = (int)p.imag()/10;
	for(int i = -1 ; i <= 1 ; i++){
		for(int j = -1 ; j <= 1 ; j++){
			for( auto next : b[x+i][y+j] ){
				if( dist(ps[next],p) <= 100 ){
					dfs(next);
				}
			}
		}
	}
}
int main(){
	int N;
	cin >> N;
	for(int i = 0 ; i < N ; i++){
		P p;
		cin >> p;
		p += P(10000,10000);
		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