Created
September 21, 2015 16:26
-
-
Save ctylim/efd0417fa7aa76795ae6 to your computer and use it in GitHub Desktop.
yukicoder No.96
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <iomanip> | |
#include <vector> | |
#include <algorithm> | |
#include <numeric> | |
#include <functional> | |
#include <cmath> | |
#include <queue> | |
#include <stack> | |
#include <map> | |
#define repd(i,a,b) for (int i=(a);i<(b);i++) | |
#define rep(i,n) repd(i,0,n) | |
typedef long long ll; | |
using namespace std; | |
int inputValue(){ | |
int a; | |
cin >> a; | |
return a; | |
} | |
void inputArray(int * p, int a){ | |
rep(i, a){ | |
cin >> p[i]; | |
} | |
} | |
void inputVector(vector<int> * p, int a){ | |
rep(i, a){ | |
int input; | |
cin >> input; | |
p -> push_back(input); | |
} | |
} | |
template <typename T> | |
void output(T a, int precision) { | |
if(precision > 0){ | |
cout << fixed << setprecision(precision) << a << "\n"; | |
} | |
else{ | |
cout << a << "\n"; | |
} | |
} | |
// 正なら反時計回り,負なら時計回り | |
int det(pair<int, int> a, pair<int, int> b){ | |
return a.first * b.second - a.second * b.first; | |
} | |
// v = q - p | |
pair<int, int> vec(pair<int, int> p, pair<int, int> q){ | |
return make_pair(q.first - p.first, q.second - p.second); | |
} | |
bool isCCW(pair<int, int> a1, pair<int, int> a2, pair<int, int> a3){ | |
pair<int, int> v1 = vec(a2, a1); | |
pair<int, int> v2 = vec(a2, a3); | |
if (det(v1, v2) >= 0) { | |
return true; | |
} | |
return false; | |
} | |
vector<pair<int, int> > convex_hull(vector<pair<int, int> > v){ | |
if (v.size() < 3) { | |
return v; | |
} | |
sort(v.begin(), v.end()); | |
// vh: 上部の凸 vl: 下部の凸 | |
vector<pair<int, int> > vh, vl; | |
// x座標の昇順に2つvhに追加 降順に2つvlに追加 | |
vh.push_back(v[0]); | |
vh.push_back(v[1]); | |
vl.push_back(v[v.size() - 1]); | |
vl.push_back(v[v.size() - 2]); | |
// vh | |
repd(i, 2, v.size()){ | |
for (int n = (int)vh.size(); n >= 2 && isCCW(vh[n - 2], vh[n - 1], v[i]); n--) { | |
vh.pop_back(); | |
} | |
vh.push_back(v[i]); | |
} | |
// vl | |
for (int i = (int)v.size() - 3; i >= 0; i--) { | |
for (int n = (int)vl.size(); n >= 2 && isCCW(vl[n - 2], vl[n - 1], v[i]); n--) { | |
vl.pop_back(); | |
} | |
vl.push_back(v[i]); | |
} | |
reverse(vl.begin(), vl.end()); | |
for (int i = (int)vh.size() - 2; i >= 1; i--) { | |
vl.push_back(vh[i]); | |
} | |
return vl; | |
} | |
vector<int> parent, rnk; | |
int root(int x){ | |
if (parent[x] == x) { | |
return x; | |
} | |
else{ | |
return root(parent[x]); | |
} | |
} | |
void unite(int x, int y){ | |
x = root(x); | |
y = root(y); | |
if (x == y) { | |
return; | |
} | |
if (rnk[x] < rnk[y]) { | |
parent[x] = y; | |
} | |
else{ | |
parent[y] = x; | |
if (rnk[x] == rnk[y]) { | |
rnk[x]++; | |
} | |
} | |
} | |
// L2ノルムの2乗 | |
int L2(pair<int, int> a, pair<int, int> b){ | |
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second); | |
} | |
vector<int> V[2001][2001]; // 4000000 | |
int main(int argc, const char * argv[]) { | |
// source code | |
int N = inputValue(); | |
vector<pair<int, int> > A(N); | |
// 縦横10の区画に入れる | |
rep(i, N){ | |
A[i] = make_pair(inputValue(), inputValue()); //(x, y) | |
V[(A[i].first + 10000) / 10][(A[i].second + 10000) / 10].push_back(i); | |
} | |
// 0個のときは1 | |
if (N == 0) { | |
output(1, 0); | |
return 0; | |
} | |
// union find init | |
parent.resize(N); | |
rnk.resize(N); | |
rep(i, N){ | |
parent[i] = i; | |
rnk[i] = 0; | |
} | |
// unite 自分と周り8区画を見る | |
rep(i, N){ | |
int x = (A[i].first + 10000) / 10; | |
int y = (A[i].second + 10000) / 10; | |
for (int dx = -1; dx <= 1; dx++) { | |
if (x + dx < 0 || x + dx > 2000) continue; | |
for (int dy = -1; dy <= 1; dy++) { | |
if (y + dy < 0 || y + dy > 2000) continue; | |
rep(j, V[x + dx][y + dy].size()){ | |
if (i == V[x + dx][y + dy][j]) continue; | |
if (L2(A[i], A[V[x + dx][y + dy][j]]) <= 100) { | |
unite(i, V[x + dx][y + dy][j]); | |
} | |
} | |
} | |
} | |
} | |
map<int, vector<int> > clst; | |
rep(i, N){ | |
clst[root(i)].push_back(i); | |
} | |
int maxDist = 0; | |
rep(i, clst.size()) { | |
if (clst[i].size() == 0) { | |
continue; | |
} | |
vector<pair<int, int> > points; | |
rep(j, clst[i].size()){ | |
points.push_back(A[clst[i][j]]); | |
} | |
vector<pair<int, int> > ch = convex_hull(points); | |
rep(p, ch.size()){ | |
rep(q, ch.size()){ | |
if (p == q) continue; | |
maxDist = max(maxDist, L2(ch[p], ch[q])); | |
} | |
} | |
} | |
output(sqrt((double)maxDist) + 2.0, 16); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment