結果

問題 No.96 圏外です。
コンテスト
ユーザー natsugir
提出日時 2014-12-07 21:08:13
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,779 bytes
コンパイル時間 1,203 ms
コンパイル使用メモリ 101,696 KB
実行使用メモリ 98,096 KB
最終ジャッジ日時 2024-06-11 17:13:23
合計ジャッジ時間 19,973 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22 TLE * 1 -- * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:116:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
main.cpp:120:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  120 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<map>
#include<cmath>
#include<complex>
#include<set>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

template<class T> inline T &amin(T &a, T b) { if (a>b) a=b; return a; }
template<class T> inline T &amax(T &a, T b) { if (a<b) a=b; return a; }
vector<int> dx, dy;
const int MAX_N = 120000;

int N;
int X[MAX_N], Y[MAX_N];
map<pair<int, int>, int> mp;
vector<int> G[MAX_N];
bool use[MAX_N];
void dfs(int v, VI &p) {
    if (use[v]) return;
    p.push_back(v);
    use[v] = true;
    REP (i, G[v].size()) {
	dfs(G[v][i], p);
    }
}

const double EPS = 1e-8;
const double INF = 1e12;
const double PI = acos(-1);

typedef complex<double> Point;
const Point I(0, 1.0);

// abs(P a) ::= sqrt(a.x^2 + a.y^2);
// norm(P a) ::= a.x^2 + a.y^2;
// Point polar(rho, theta=0)

int sign(double x) {
    if (x < EPS) return -1;
    if (x > EPS) return 1;
    return 0;
}

namespace std {
    bool operator <(const Point &x, const Point &y) {
	return real(x)!=real(y)?real(x)<real(y):imag(x)<imag(y);
    }
}

double cross(const Point &x, const Point &y) {
    return imag(conj(x)*y);
}
double dot(const Point &x, const Point &y) {
    return real(conj(x)*y);
}

int ccw(Point a, Point b, Point 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;
}
VI convex(VI v) {
    if (v.size() < 3u) return v;
    vector<Point> ps;
    REP (i, v.size()) ps.push_back(Point(X[v[i]], Y[v[i]]));
    
    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);

    VI ret;
    REP (i, ch.size()) {
	int x = ch[i].real();
	int y = ch[i].imag();
	ret.push_back(mp[make_pair(x, y)]);
    }
    return ret;
}

int sq(int x) { return x*x; }
int sqsum(int i, int j) {
    return sq(X[i] - X[j]) + sq(Y[i] - Y[j]);
}
double hypot(int i, int j) { return sqrt(sqsum(i, j)); }

int main() {
    for (int y=-11; y<=11; y++) {
	for (int x=-11; x<=11; x++) {
	    if (x*x + y*y <= 100) {
		dx.push_back(x);
		dy.push_back(y);
	    }
	}
    }

    
    scanf("%d", &N);
    int cnt = 0;
    REP (i, N) {
	int x, y;
	scanf("%d%d", &x, &y);
	pair<int, int> k(x, y);
	if (mp.count(k) == 0) mp[k] = cnt++;
    }

    N = cnt;
    EACH (it, mp) {
	int v = it->second;
	int x = it->first.first;
	int y = it->first.second;
	X[v] = x; Y[v] = y;
	
	REP (d, dx.size()) {
	    pair<int, int> k(x+dx[d], y+dy[d]);
	    if (mp.count(k)) G[v].push_back(mp[k]);
	}
    }

    vector<vector<int> > C;
    memset(use, 0, sizeof use);
    REP (i, N) {
	if (!use[i]) {
	    vector<int> p;
	    dfs(i, p);
	    C.push_back(p);
	}
    }

    double ans = 1.0;
    REP (i, C.size()) {
	VI v = C[i];
	VI h = convex(v);
	int M = h.size();
	for (int i=0, j=0; i<(int)h.size(); i++) {
	    while (true) {
		int nxt = (j+1) % M;
		if (sqsum(h[i], h[j]) < sqsum(h[i], h[nxt])) {
		    j = nxt;
		} else {
		    break;
		}
	    }
	    amax(ans, hypot(h[i], h[j])+2.0);
	}
    }

    printf("%.9f\n", ans);
    
    return 0;
}
0