結果

問題 No.96 圏外です。
ユーザー antaanta
提出日時 2014-12-07 20:40:34
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 330 ms / 5,000 ms
コード長 6,755 bytes
コンパイル時間 1,223 ms
コンパイル使用メモリ 106,656 KB
実行使用メモリ 63,048 KB
最終ジャッジ日時 2023-08-26 04:21:47
合計ジャッジ時間 6,840 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
51,912 KB
testcase_01 AC 15 ms
51,812 KB
testcase_02 AC 14 ms
51,916 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 20 ms
52,304 KB
testcase_05 AC 22 ms
52,176 KB
testcase_06 AC 26 ms
52,452 KB
testcase_07 AC 30 ms
52,704 KB
testcase_08 AC 41 ms
52,772 KB
testcase_09 AC 48 ms
53,112 KB
testcase_10 AC 54 ms
53,496 KB
testcase_11 AC 74 ms
54,248 KB
testcase_12 AC 129 ms
54,260 KB
testcase_13 AC 98 ms
55,296 KB
testcase_14 AC 143 ms
55,672 KB
testcase_15 AC 148 ms
56,832 KB
testcase_16 AC 200 ms
57,424 KB
testcase_17 AC 330 ms
58,412 KB
testcase_18 AC 262 ms
58,412 KB
testcase_19 AC 257 ms
58,468 KB
testcase_20 AC 180 ms
59,944 KB
testcase_21 AC 159 ms
61,056 KB
testcase_22 AC 144 ms
62,932 KB
testcase_23 AC 149 ms
63,048 KB
testcase_24 AC 15 ms
51,848 KB
testcase_25 AC 232 ms
56,404 KB
testcase_26 AC 291 ms
57,792 KB
testcase_27 AC 259 ms
56,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <unordered_map>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

const int C = 317;
const int circle[C] = {-200210,-180193,-180192,-180191,-180190,-180189,-180188,-180187,-180186,-180185,-160174,-160173,-160172,-160171,-160170,-160169,-160168,-160167,-160166,-160165,-160164,-160163,-160162,-140154,-140153,-140152,-140151,-140150,-140149,-140148,-140147,-140146,-140145,-140144,-140143,-140142,-140141,-140140,-120134,-120133,-120132,-120131,-120130,-120129,-120128,-120127,-120126,-120125,-120124,-120123,-120122,-120121,-120120,-120119,-120118,-100113,-100112,-100111,-100110,-100109,-100108,-100107,-100106,-100105,-100104,-100103,-100102,-100101,-100100,-100099,-100098,-100097,-80093,-80092,-80091,-80090,-80089,-80088,-80087,-80086,-80085,-80084,-80083,-80082,-80081,-80080,-80079,-80078,-80077,-80076,-80075,-60072,-60071,-60070,-60069,-60068,-60067,-60066,-60065,-60064,-60063,-60062,-60061,-60060,-60059,-60058,-60057,-60056,-60055,-60054,-40051,-40050,-40049,-40048,-40047,-40046,-40045,-40044,-40043,-40042,-40041,-40040,-40039,-40038,-40037,-40036,-40035,-40034,-40033,-20030,-20029,-20028,-20027,-20026,-20025,-20024,-20023,-20022,-20021,-20020,-20019,-20018,-20017,-20016,-20015,-20014,-20013,-20012,-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,20012,20013,20014,20015,20016,20017,20018,20019,20020,20021,20022,20023,20024,20025,20026,20027,20028,20029,20030,40033,40034,40035,40036,40037,40038,40039,40040,40041,40042,40043,40044,40045,40046,40047,40048,40049,40050,40051,60054,60055,60056,60057,60058,60059,60060,60061,60062,60063,60064,60065,60066,60067,60068,60069,60070,60071,60072,80075,80076,80077,80078,80079,80080,80081,80082,80083,80084,80085,80086,80087,80088,80089,80090,80091,80092,80093,100097,100098,100099,100100,100101,100102,100103,100104,100105,100106,100107,100108,100109,100110,100111,100112,100113,120118,120119,120120,120121,120122,120123,120124,120125,120126,120127,120128,120129,120130,120131,120132,120133,120134,140140,140141,140142,140143,140144,140145,140146,140147,140148,140149,140150,140151,140152,140153,140154,160162,160163,160164,160165,160166,160167,160168,160169,160170,160171,160172,160173,160174,180185,180186,180187,180188,180189,180190,180191,180192,180193,200210};
int sq(int x) { return x*x; }

int pack(int y, int x) {
	return (y + 10011) * 20021 + (x + 10011);
}

struct P {
	typedef int T; typedef ll T2;	//T2は{a*b | a:T, b:T}を含むタイプ
	T x, y;
	P(T x_, T y_): x(x_), y(y_) {}
	P(): x(0), y(0) {}
};
inline bool operator==(const P& a, const P& b) { return a.x == b.x && a.y == b.y; }
inline bool operator<(const P& a, const P& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
inline P operator+(const P& a, const P& b) { return P(a.x+b.x, a.y+b.y); }
inline P operator-(const P& a, const P& b) { return P(a.x-b.x, a.y-b.y); }
inline P operator-=(P& a, const P& b) { a.x -= b.x, a.y -= b.y ; return a; }
inline P::T2 cross(const P& a, const P& b) { return (P::T2)a.x*b.y - (P::T2)a.y*b.x; }
inline P::T2 dot(const P& a, const P& b) { return (P::T2)a.x*b.x + (P::T2)a.y*b.y; }
inline P::T2 norm(const P& a) { return (P::T2)a.x*a.x + (P::T2)a.y*a.y; }
ostream& operator<<(ostream& out, const P& x) { out << "(" << x.x << ", " << x.y << ")"; return out; }

struct L {
	P a, b;
	L(const P &a_, const P &b_): a(a_), b(b_) {}
	const P& operator[](size_t i) const { return i ? b : a; }
};

inline int ccw(const P& a, const P& b, const P& c) {
	int ax = b.x - a.x, ay = b.y - a.y, bx = c.x - a.x, by = c.y - a.y;
	P::T2 t = (P::T2)ax*by - (P::T2)ay*bx;
	if (t > 0) return 1;
	if (t < 0) return -1;
	if((P::T2)ax*bx + (P::T2)ay*by < 0) return +2;
	if((P::T2)ax*ax + (P::T2)ay*ay < (P::T2)bx*bx + (P::T2)by*by) return -2;
	return 0;
}

vector<P> convex_hull(vector<P> ps) {
	int n = ps.size(), k = 0;
	sort(ps.begin(), ps.end());
	vector<P> 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;
}

int main() {
	int N;
	cin >> N;
	vector<int> X(N), Y(N);
	rep(i, N)
		scanf("%d%d", &X[i], &Y[i]);
	if(N == 0) {
		puts("1");
		return 0;
	}
	vector<bool> bv(20021*20021);
	map<int,int> a;
	rep(i, N) {
		int p = pack(Y[i],X[i]);
		a.insert(mp(p, i));
		bv[p] = true;
	}
	vector<bool> vis(N);
	ll maxd = 0;
	vector<P> points;
	vi stk;
	rep(s, N) if(!vis[s]) {
		stk.clear();
		points.clear();
		stk.push_back(s);
		vis[s] = true;
		bv[pack(Y[s], X[s])] = false;
//		cerr << s << ": " << endl;
		while(!stk.empty()) {
			int i = stk.back(); stk.pop_back();
			int y0 = Y[i], x0 = X[i];
//			cerr << "\t" << i << endl;
			points.push_back(P(x0, y0));
			int p0 = pack(y0, x0);
			rep(k, C) {
				int p = p0 + circle[k];
				if(bv[p]) {
					auto it = a.find(p);
					if(it != a.end()) {
						int j = it->second;
						if(!vis[j]) {
							stk.push_back(j);
							vis[j] = true;
						}
						bv[p] = false;
					}
				}
			}
		}
		if(points.size() >= 2) {
			vector<P> ch = convex_hull(points);
			ll d = 0;
			rep(i, ch.size()) rep(j, i)
				amax(d, norm(ch[i] - ch[j]));
			amax(maxd, d);
		}
	}
	double ans = sqrt(maxd * 1.) + 2;
	printf("%.10f\n", ans);
	return 0;
}
0