#138928 (C++11) No.96 圏外です。

提出ソース

結果

問題	No.96 圏外です。
ユーザー	assy1028
提出日時	2016-12-16 00:39:55
言語	C++11 (gcc 11.4.0)
結果	TLE
実行時間	-
コード長	5,140 bytes
コンパイル時間	1,813 ms
コンパイル使用メモリ	126,968 KB
実行使用メモリ	21,956 KB
最終ジャッジ日時	2024-05-07 15:30:32
合計ジャッジ時間	10,211 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 10,012 KB
testcase_01	AC	4 ms 9,536 KB
testcase_02	AC	4 ms 9,628 KB
testcase_03	AC	4 ms 8,332 KB
testcase_04	AC	23 ms 9,356 KB
testcase_05	AC	47 ms 9,320 KB
testcase_06	AC	78 ms 9,920 KB
testcase_07	AC	140 ms 10,576 KB
testcase_08	AC	186 ms 11,668 KB
testcase_09	AC	286 ms 11,468 KB
testcase_10	TLE	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 != is || j != js);
    return maxd;
    // farthest pair is (maxi, maxj).
}

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;
    map<pair<int, int>, int> 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]);
            }
        }
    }
    
    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) {
            res = max(res, 2.0+convex_diameter(convex_hull(g[v])));
        }
    }
    
    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;
}

yukicoder

結果

テストケース

ソースコード