結果

問題 No.96 圏外です。
ユーザー nodchipnodchip
提出日時 2014-12-07 21:43:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 483 ms / 5,000 ms
コード長 5,545 bytes
コンパイル時間 1,156 ms
コンパイル使用メモリ 122,440 KB
実行使用メモリ 145,852 KB
最終ジャッジ日時 2023-08-25 21:25:32
合計ジャッジ時間 7,178 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
101,896 KB
testcase_01 AC 48 ms
101,808 KB
testcase_02 AC 47 ms
101,932 KB
testcase_03 AC 47 ms
102,040 KB
testcase_04 AC 51 ms
102,916 KB
testcase_05 AC 54 ms
103,832 KB
testcase_06 AC 57 ms
104,764 KB
testcase_07 AC 62 ms
105,084 KB
testcase_08 AC 72 ms
107,180 KB
testcase_09 AC 82 ms
108,856 KB
testcase_10 AC 89 ms
108,268 KB
testcase_11 AC 107 ms
113,328 KB
testcase_12 AC 122 ms
119,304 KB
testcase_13 AC 138 ms
112,648 KB
testcase_14 AC 174 ms
121,208 KB
testcase_15 AC 183 ms
115,820 KB
testcase_16 AC 236 ms
127,656 KB
testcase_17 AC 267 ms
145,852 KB
testcase_18 AC 283 ms
130,996 KB
testcase_19 AC 290 ms
131,160 KB
testcase_20 AC 189 ms
118,644 KB
testcase_21 AC 236 ms
119,076 KB
testcase_22 AC 475 ms
116,676 KB
testcase_23 AC 483 ms
116,412 KB
testcase_24 AC 47 ms
101,808 KB
testcase_25 AC 202 ms
133,556 KB
testcase_26 AC 251 ms
142,064 KB
testcase_27 AC 221 ms
136,984 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
#include <locale>
#include <memory>
#include <stdexcept>
#include <utility>
#include <string>
#include <fstream>
#include <ios>
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <streambuf>
#include <complex>
#include <numeric>
#include <valarray>
#include <exception>
#include <limits>
#include <new>
#include <typeinfo>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <climits>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdlib>
#include <cstddef>
#include <cstdarg>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <cwchar>
#include <cwctype>
using namespace std;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);
typedef long long ll;
typedef unsigned long long ull;

#define ALL(c) (c).begin(), (c).end()
#define CLEAR(v) memset(v,0,sizeof(v))
#define MP(a,b) make_pair((a),(b))
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define ABS(a) ((a)>0?(a):-(a))
template<class T> T MIN(const T& a, const T& b) { return a < b ? a : b; }
template<class T> T MAX(const T& a, const T& b) { return a > b ? a : b; }
template<class T> void MIN_UPDATE(T& a, const T& b) { if (a > b) a = b; }
template<class T> void MAX_UPDATE(T& a, const T& b) { if (a < b) a = b; }

typedef complex<double> P;

const double INF = 1e12;
typedef complex<double> P;
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;
}

bool cmp_x(const P& p, const P& q) {
	if (p.real() != q.real()) return p.real() < q.real();
	return p.imag() < q.imag();
}

vector<P> convex_hull(P* ps, int n) {
	sort(ps, ps + n, cmp_x);
	int k = 0;
	vector<P> qs(n * 2);
	REP(i, n) {
		while (k > 1 && cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 1]) <= 0) --k;
		qs[k++] = ps[i];
	}
	for (int i = n - 2, t = k; i >= 0; --i) {
		while (k > t && cross(qs[k - 1] - qs[k - 2], ps[i] - qs[k - 1]) <= 0) --k;
		qs[k++] = ps[i];
	}
	qs.resize(k - 1);
	return qs;
}

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int main() {
	std::ios::sync_with_stdio(false);

	int N;
	cin >> N;
	vector<int> X;
	vector<int> Y;
	vector<P> pos;
	REP(n, N) {
		int x, y;
		cin >> x >> y;
		pos.push_back(P(x, y));
		X.push_back(x);
		Y.push_back(y);
	}

	static vector<int> cells[2048][2048];
	REP(n, N) {
		int x = X[n];
		int y = Y[n];

		int cellX = (x + 10000) / 10;
		int cellY = (y + 10000) / 10;
		REP(dx, 3) REP(dy, 3) {
			cells[cellX + dx][cellY + dy].push_back(n);
		}
	}

	UnionFind uf(N);
	REP(cellX, 2048) {
		REP(cellY, 2048) {
			const auto& ps = cells[cellX][cellY];
			REP(i, ps.size()) {
				REP(j, i) {
					if ((X[ps[i]] - X[ps[j]]) * (X[ps[i]] - X[ps[j]]) + (Y[ps[i]] - Y[ps[j]]) * (Y[ps[i]] - Y[ps[j]]) <= 100) {
						uf.unionSet(ps[i], ps[j]);
					}
				}
			}
		}
	}

	map<int, vector<P> > points;
	REP(i, N) {
		points[uf.root(i)].push_back(pos[i]);
	}

	double answer = 1.0;
	//int counter = 0;
	//cerr << "points.size(): " << points.size() << endl;
	for (auto& connected : points) {
		//if (counter == 15281) {
		//	int temp = 0;
		//}
		//if (15200 <= counter && counter <= 15300) {
		//	cerr << counter << endl;
		//}
		//++counter;

		int n = connected.second.size();
		if (n == 1) {
			MAX_UPDATE(answer, 2.0);
			continue;
		}

		if (n == 2) {
			MAX_UPDATE(answer, abs(connected.second[0] - connected.second[1]) + 2.0);
			continue;
		}

		vector<P> qs = convex_hull(&connected.second[0], connected.second.size());
		n = qs.size();

		if (n < 10) {
			REP(i, n) REP(j, i) {
				MAX_UPDATE(answer, abs(qs[i] - qs[j]) + 2.0);
			}
			continue;
		}

		int i = 0;
		int j = 0;
		for (int k = 0; k < n; ++k) {
			if (!cmp_x(qs[i], qs[k])) i = k;
			if (cmp_x(qs[j], qs[k])) j = k;
		}
		int si = i, sj = j;
		while (i != sj || j != si) {
			MAX_UPDATE(answer, abs(qs[i] - qs[j]) + 2.0);
			if (cross(qs[(i + 1) % n] - qs[i], qs[(j + 1) % n] - qs[j]) < 0) {
				i = (i + 1) % n;
			}
			else {
				j = (j + 1) % n;
			}
		}
	}

	printf("%.20f\n", answer);
}
0