結果

問題 No.96 圏外です。
ユーザー assy1028assy1028
提出日時 2016-12-16 01:29:15
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2,837 ms / 5,000 ms
コード長 5,650 bytes
コンパイル時間 1,598 ms
コンパイル使用メモリ 129,524 KB
実行使用メモリ 30,936 KB
最終ジャッジ日時 2024-06-06 16:35:10
合計ジャッジ時間 26,096 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
8,500 KB
testcase_01 AC 4 ms
9,948 KB
testcase_02 AC 5 ms
8,468 KB
testcase_03 AC 4 ms
7,496 KB
testcase_04 AC 25 ms
11,684 KB
testcase_05 AC 51 ms
9,348 KB
testcase_06 AC 72 ms
9,120 KB
testcase_07 AC 134 ms
10,372 KB
testcase_08 AC 158 ms
13,224 KB
testcase_09 AC 282 ms
11,144 KB
testcase_10 AC 331 ms
12,412 KB
testcase_11 AC 494 ms
13,052 KB
testcase_12 AC 491 ms
16,936 KB
testcase_13 AC 808 ms
17,560 KB
testcase_14 AC 1,072 ms
20,364 KB
testcase_15 AC 1,637 ms
20,812 KB
testcase_16 AC 1,410 ms
24,048 KB
testcase_17 AC 1,770 ms
28,580 KB
testcase_18 AC 2,081 ms
27,192 KB
testcase_19 AC 2,095 ms
27,068 KB
testcase_20 AC 1,386 ms
25,316 KB
testcase_21 AC 1,275 ms
28,548 KB
testcase_22 AC 2,837 ms
30,776 KB
testcase_23 AC 969 ms
30,936 KB
testcase_24 AC 4 ms
8,776 KB
testcase_25 AC 1,423 ms
22,912 KB
testcase_26 AC 1,459 ms
26,800 KB
testcase_27 AC 1,119 ms
25,132 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const ll mod = 1e9 + 7;
const double pi = acos(-1);

typedef long double D;
typedef complex<D> P;
typedef vector<P> Poly, ConvexPoly;

const D inf = 1e12, eps = 1e-10;

#define X real()
#define Y imag()

int sig(D a, D b=0) {return a < b-eps ? -1 : (a > b+eps ? 1 : 0);}
template<typename T> bool eq(const T& a, const T& b) {return sig(abs(a-b)) == 0;}
bool compX(const P& a, const P& b) {return !eq(a.X, b.X) ? sig(a.X, b.X) < 0 : sig(a.Y, b.Y) < 0;}
namespace std {
    bool operator < (const P& a, const P& b) {return compX(a, b);}
    bool operator == (const P& a, const P& b) {return eq(a,b);}
};
D cross(const P& a, const P& b) {return imag(conj(a) * b);}
D dot(const P& a, const P& b) {return real(conj(a) * b);}

int ccw(const P& a, P b, P c) {
    b -= a; c -= a;
    if (sig(cross(b, c)) > 0) return 1;    //counter clockwise
    if (sig(cross(b, c)) < 0) return -1;   //clockwise
    if (sig(dot(b, c)) < 0) return 2;      //c--a--b on line
    if (sig(norm(b), norm(c))) return -2;   //a--b--c on line
    return 0; //a--c--b on line
}

// 凸包
// O(n logn)
ConvexPoly convex_hull(Poly& ps) {
    int n = ps.size(), k = 0;
    sort(ALL(ps));
    Poly ch(2*n);
    for (int i = 0; i < n; i++) {
	while (k > 1 && cross(ch[k-1]-ch[k-2], ps[i]-ch[k-1]) < 0) k--;
	ch[k++] = ps[i];
    }
    for (int i = n-2, t = k; i >= 0; i--) {
	while (k > t && cross(ch[k-1]-ch[k-2], ps[i]-ch[k-1]) < 0) k--;
	ch[k++] = ps[i];
    }
    ch.resize(k-1);
    return ch;
}

// 凸多角形の直径
// O(n)
D convex_diameter(const ConvexPoly& ps) {
    const int l = ps.size();
    int is = 0, js = 0;
    for (int i = 0; i < l; i++) if (ps[i].Y > ps[is].Y) is = i;
    for (int j = 0; j < l; j++) if (ps[j].Y < ps[js].Y) js = j;
    D maxd = abs(ps[is] - ps[js]);

    int i = is, maxi = is, j = js, maxj = js;
    do {
        if (cross(ps[(i+1)%l]-ps[i], ps[(j+1)%l]-ps[j]) >= 0) j = (j+1)%l;
        else i = (i+1)%l;
        D dis = abs(ps[i]-ps[j]);
        if (dis > maxd) {
            maxd = dis;
            maxi = i;
            maxj = j;
        }
    } while (i != js || j != is);
    return maxd;
    // farthest pair is (maxi, maxj).
}

D area2(const Poly& ps) {
    D res = 0;
    int n = ps.size();
    for (int i = 0; i < n; i++)
	res += cross(ps[i], ps[(i+1)%n]);
    return res;
}

class UnionFind {
private:
    static const int MAX = 120010;
    int par[MAX];
    int r[MAX];
public:
    UnionFind(int n = MAX) {
        for (int i = 0; i < n; i++) {
            par[i] = i;
            r[i] = 0;
        }
    }

    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (r[x] < r[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (r[x] == r[y]) r[x]++;
        }
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

int n;
pair<int, int> xy[120010];
P p[120010];
Poly g[120010];

D dist(D x0, D y0, D x1, D y1) {
    return sqrt((x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1));
}

D solve() {
    if (n == 0) return 1.0;
    unordered_map<pair<int, int>, int, pairhash> memo;
    for (int i = 0; i < n; i++) memo[xy[i]] = i;
    vector<pair<int, int> > vec;
    for (int dy = -10; dy <= 10; dy++) {
        for (int dx = -10; dx <= 10; dx++) {
            if (!(dx==0&&dy==0) && dist(0, 0, dx, dy) < 10.0+eps)
                vec.push_back(make_pair(dx, dy));
        }
    }
    
    UnionFind uf(n);
    int l = vec.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < l; j++) {
            pair<int, int> XY = make_pair(xy[i].first+vec[j].first, xy[i].second+vec[j].second);
            if (memo.count(XY) > 0) {
                uf.unite(i, memo[XY]);
            }
        }
    }
    
    unordered_set<int> s;
    for (int i = 0; i < n; i++) {
        int v = uf.find(i);
        s.insert(v);
        g[v].push_back(p[i]);
    }

    D res = 2.0;
    for (int v : s) {
        int k = g[v].size();
        if (k == 2) res = max(res, 2.0+dist(g[v][0].X, g[v][0].Y, g[v][1].X, g[v][1].Y));
        else if (k > 2) {
            ConvexPoly cp = convex_hull(g[v]);
            if (area2(cp) < eps) {
                res = max(res, 2.0+dist(g[v][0].X, g[v][0].Y, g[v][k-1].X, g[v][k-1].Y));
            } else {
                res = max(res, 2.0+convex_diameter(cp));
            }
        }
    }
    
    return res;
}

void input() {
    cin >> n;
    int x, y;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        xy[i] = make_pair(x, y);
        p[i] = P(x, y);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    input();
    cout << solve() << endl;
}
0