結果

問題 No.96 圏外です。
ユーザー assy1028assy1028
提出日時 2016-12-16 01:29:15
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3,389 ms / 5,000 ms
コード長 5,650 bytes
コンパイル時間 1,240 ms
コンパイル使用メモリ 125,288 KB
実行使用メモリ 30,952 KB
最終ジャッジ日時 2023-08-25 22:07:19
合計ジャッジ時間 30,147 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
7,728 KB
testcase_01 AC 4 ms
7,724 KB
testcase_02 AC 4 ms
7,716 KB
testcase_03 AC 4 ms
7,808 KB
testcase_04 AC 27 ms
8,296 KB
testcase_05 AC 57 ms
8,336 KB
testcase_06 AC 80 ms
9,036 KB
testcase_07 AC 150 ms
9,248 KB
testcase_08 AC 179 ms
9,796 KB
testcase_09 AC 299 ms
10,424 KB
testcase_10 AC 356 ms
11,348 KB
testcase_11 AC 542 ms
12,624 KB
testcase_12 AC 547 ms
17,172 KB
testcase_13 AC 913 ms
16,880 KB
testcase_14 AC 1,215 ms
19,680 KB
testcase_15 AC 1,934 ms
19,928 KB
testcase_16 AC 1,645 ms
24,196 KB
testcase_17 AC 2,079 ms
28,380 KB
testcase_18 AC 2,321 ms
27,064 KB
testcase_19 AC 2,306 ms
27,068 KB
testcase_20 AC 1,738 ms
25,284 KB
testcase_21 AC 1,522 ms
28,024 KB
testcase_22 AC 3,389 ms
30,952 KB
testcase_23 AC 1,212 ms
30,812 KB
testcase_24 AC 4 ms
7,760 KB
testcase_25 AC 1,601 ms
22,192 KB
testcase_26 AC 1,664 ms
26,676 KB
testcase_27 AC 1,467 ms
25,084 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