結果

問題 No.96 圏外です。
ユーザー yuustiyuusti
提出日時 2014-12-08 23:25:10
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,356 bytes
コンパイル時間 1,259 ms
コンパイル使用メモリ 119,208 KB
実行使用メモリ 14,596 KB
最終ジャッジ日時 2024-06-11 18:32:47
合計ジャッジ時間 8,092 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 WA -
testcase_04 AC 3 ms
5,504 KB
testcase_05 AC 5 ms
5,760 KB
testcase_06 AC 8 ms
5,888 KB
testcase_07 AC 13 ms
6,272 KB
testcase_08 AC 16 ms
6,784 KB
testcase_09 AC 24 ms
7,268 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <climits>
#include <bitset>
#include <cassert>
#include <random>
#include <complex>

#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end())
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long ll;
//typedef pair<int, int> P;

const double EPS = 1e-8;
const double INF = 1e12;

typedef complex<double> P;
typedef P point;

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

typedef vector<P> G;

struct C {
	P p; double r;
	C(const P &p, double r) : p(p), r(r) { }
};
int ccw(P a, P b, P c) {
	b -= a; c -= a;
	if (cross(b, c) > 0)   return +1;       // counter clockwise
	if (cross(b, c) < 0)   return -1;       // clockwise
	if (dot(b, c) < 0)     return +2;       // c--a--b on line
	if (norm(b) < norm(c)) return -2;       // a--b--c on line
	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;
}

typedef double number;
typedef vector<P> polygon;

#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]
#define diff(P, i) (next(P, i) - curr(P, i))
number convex_diameter(const polygon &pt) {
	const int n = pt.size();
	int is = 0, js = 0;
	for (int i = 1; i < n; ++i) {
		if (imag(pt[i]) > imag(pt[is])) is = i;
		if (imag(pt[i]) < imag(pt[js])) js = i;
	}
	number maxd = norm(pt[is] - pt[js]);

	int i, maxi, j, maxj;
	i = maxi = is;
	j = maxj = js;
	do {
		if (cross(diff(pt, i), diff(pt, j)) >= 0) j = (j + 1) % n;
		else i = (i + 1) % n;
		if (norm(pt[i] - pt[j]) > maxd) {
			maxd = norm(pt[i] - pt[j]);
			maxi = i; maxj = j;
		}
	} while (i != is || j != js);
	return maxd; /* farthest pair is (maxi, maxj). */
}

const int N = 120010;
struct UnionFind{
	int par[N];

	UnionFind(int n){
		iota(par, par + n, 0);
	}
	int find(int x){
		if (par[x] == x) return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y){
		par[find(x)] = find(y);
	}
};

const int X = 10020;
map<int, int> yy[20050];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<P> vp;
	rep(i, n){
		int x, y;
		cin >> x >> y;
		vp.emplace_back(P(x, y));
		yy[X + x][y] = i;
	}

	UnionFind uf(n);
	rep(i, n){
		int x = X + vp[i].real();
		int y = vp[i].imag();
		for (int dx = -10; dx <= 10; ++dx){
			int dy = sqrt(100 - dx*dx);
			if (yy[x + dx].empty()) continue;
			auto it1 = yy[x + dx].lower_bound(y - dy);
			auto it2 = yy[x + dx].upper_bound(y + dy);
			while (it1 != it2){
				uf.unite(i, it1->second);
				++it1;
			}
		}
	}

	vector<int> num(n);
	rep(i, n) num[i] = uf.find(i);
	sort(ALL(num));
	UNIQUE(num);
	auto get = [&](int x){return lower_bound(ALL(num), x) - num.begin(); };

	vector<vector<P>> gr(num.size());
	rep(i, n) gr[get(uf.find(i))].push_back(vp[i]);

	double ans = 0;
	for (auto poly : gr){
        if (poly.size() <= 2){
			if(poly.size() != 1) ans = max(ans, abs(poly[0] - poly[1]));
		}
		else{
			ans = max(ans, sqrt(convex_diameter(convex_hull(poly))));
		}
	}
	cout.setf(ios::fixed);
	cout.precision(12);

	cout << ans + 2 << endl;

	return 0;
}
0