結果
| 問題 |
No.96 圏外です。
|
| コンテスト | |
| ユーザー |
 anta
|
| 提出日時 | 2014-12-07 19:39:40 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,208 bytes |
| コンパイル時間 | 1,137 ms |
| コンパイル使用メモリ | 107,784 KB |
| 実行使用メモリ | 13,888 KB |
| 最終ジャッジ日時 | 2024-06-11 16:12:07 |
| 合計ジャッジ時間 | 8,303 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 TLE * 1 -- * 17 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:123:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
123 | scanf("%d%d", &X[i], &Y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <unordered_map>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
const int C = 317;
const int circle[C][2] = {{-10,0},{-9,-4},{-9,-3},{-9,-2},{-9,-1},{-9,0},{-9,1},{-9,2},{-9,3},{-9,4},{-8,-6},{-8,-5},{-8,-4},{-8,-3},{-8,-2},{-8,-1},{-8,0},{-8,1},{-8,2},{-8,3},{-8,4},{-8,5},{-8,6},{-7,-7},{-7,-6},{-7,-5},{-7,-4},{-7,-3},{-7,-2},{-7,-1},{-7,0},{-7,1},{-7,2},{-7,3},{-7,4},{-7,5},{-7,6},{-7,7},{-6,-8},{-6,-7},{-6,-6},{-6,-5},{-6,-4},{-6,-3},{-6,-2},{-6,-1},{-6,0},{-6,1},{-6,2},{-6,3},{-6,4},{-6,5},{-6,6},{-6,7},{-6,8},{-5,-8},{-5,-7},{-5,-6},{-5,-5},{-5,-4},{-5,-3},{-5,-2},{-5,-1},{-5,0},{-5,1},{-5,2},{-5,3},{-5,4},{-5,5},{-5,6},{-5,7},{-5,8},{-4,-9},{-4,-8},{-4,-7},{-4,-6},{-4,-5},{-4,-4},{-4,-3},{-4,-2},{-4,-1},{-4,0},{-4,1},{-4,2},{-4,3},{-4,4},{-4,5},{-4,6},{-4,7},{-4,8},{-4,9},{-3,-9},{-3,-8},{-3,-7},{-3,-6},{-3,-5},{-3,-4},{-3,-3},{-3,-2},{-3,-1},{-3,0},{-3,1},{-3,2},{-3,3},{-3,4},{-3,5},{-3,6},{-3,7},{-3,8},{-3,9},{-2,-9},{-2,-8},{-2,-7},{-2,-6},{-2,-5},{-2,-4},{-2,-3},{-2,-2},{-2,-1},{-2,0},{-2,1},{-2,2},{-2,3},{-2,4},{-2,5},{-2,6},{-2,7},{-2,8},{-2,9},{-1,-9},{-1,-8},{-1,-7},{-1,-6},{-1,-5},{-1,-4},{-1,-3},{-1,-2},{-1,-1},{-1,0},{-1,1},{-1,2},{-1,3},{-1,4},{-1,5},{-1,6},{-1,7},{-1,8},{-1,9},{0,-10},{0,-9},{0,-8},{0,-7},{0,-6},{0,-5},{0,-4},{0,-3},{0,-2},{0,-1},{0,0},{0,1},{0,2},{0,3},{0,4},{0,5},{0,6},{0,7},{0,8},{0,9},{0,10},{1,-9},{1,-8},{1,-7},{1,-6},{1,-5},{1,-4},{1,-3},{1,-2},{1,-1},{1,0},{1,1},{1,2},{1,3},{1,4},{1,5},{1,6},{1,7},{1,8},{1,9},{2,-9},{2,-8},{2,-7},{2,-6},{2,-5},{2,-4},{2,-3},{2,-2},{2,-1},{2,0},{2,1},{2,2},{2,3},{2,4},{2,5},{2,6},{2,7},{2,8},{2,9},{3,-9},{3,-8},{3,-7},{3,-6},{3,-5},{3,-4},{3,-3},{3,-2},{3,-1},{3,0},{3,1},{3,2},{3,3},{3,4},{3,5},{3,6},{3,7},{3,8},{3,9},{4,-9},{4,-8},{4,-7},{4,-6},{4,-5},{4,-4},{4,-3},{4,-2},{4,-1},{4,0},{4,1},{4,2},{4,3},{4,4},{4,5},{4,6},{4,7},{4,8},{4,9},{5,-8},{5,-7},{5,-6},{5,-5},{5,-4},{5,-3},{5,-2},{5,-1},{5,0},{5,1},{5,2},{5,3},{5,4},{5,5},{5,6},{5,7},{5,8},{6,-8},{6,-7},{6,-6},{6,-5},{6,-4},{6,-3},{6,-2},{6,-1},{6,0},{6,1},{6,2},{6,3},{6,4},{6,5},{6,6},{6,7},{6,8},{7,-7},{7,-6},{7,-5},{7,-4},{7,-3},{7,-2},{7,-1},{7,0},{7,1},{7,2},{7,3},{7,4},{7,5},{7,6},{7,7},{8,-6},{8,-5},{8,-4},{8,-3},{8,-2},{8,-1},{8,0},{8,1},{8,2},{8,3},{8,4},{8,5},{8,6},{9,-4},{9,-3},{9,-2},{9,-1},{9,0},{9,1},{9,2},{9,3},{9,4},{10,0}};
int sq(int x) { return x*x; }
int pack(int y, int x) {
return (y + 10011) * 20021 + (x + 10011);
}
struct P {
typedef int T; typedef ll T2; //T2は{a*b | a:T, b:T}を含むタイプ
T x, y;
P(T x_, T y_): x(x_), y(y_) {}
P(): x(0), y(0) {}
};
inline bool operator==(const P& a, const P& b) { return a.x == b.x && a.y == b.y; }
inline bool operator<(const P& a, const P& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
inline P operator+(const P& a, const P& b) { return P(a.x+b.x, a.y+b.y); }
inline P operator-(const P& a, const P& b) { return P(a.x-b.x, a.y-b.y); }
inline P operator-=(P& a, const P& b) { a.x -= b.x, a.y -= b.y ; return a; }
inline P::T2 cross(const P& a, const P& b) { return (P::T2)a.x*b.y - (P::T2)a.y*b.x; }
inline P::T2 dot(const P& a, const P& b) { return (P::T2)a.x*b.x + (P::T2)a.y*b.y; }
inline P::T2 norm(const P& a) { return (P::T2)a.x*a.x + (P::T2)a.y*a.y; }
ostream& operator<<(ostream& out, const P& x) { out << "(" << x.x << ", " << x.y << ")"; return out; }
struct L {
P a, b;
L(const P &a_, const P &b_): a(a_), b(b_) {}
const P& operator[](size_t i) const { return i ? b : a; }
};
inline int ccw(const P& a, const P& b, const P& c) {
int ax = b.x - a.x, ay = b.y - a.y, bx = c.x - a.x, by = c.y - a.y;
P::T2 t = (P::T2)ax*by - (P::T2)ay*bx;
if (t > 0) return 1;
if (t < 0) return -1;
if((P::T2)ax*bx + (P::T2)ay*by < 0) return +2;
if((P::T2)ax*ax + (P::T2)ay*ay < (P::T2)bx*bx + (P::T2)by*by) return -2;
return 0;
}
vector<P> convex_hull(vector<P> ps) {
int n = ps.size(), k = 0;
sort(ps.begin(), ps.end());
vector<P> 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);
return ch;
}
ll convex_diameter(const vector<P> &pt) {
const int n = pt.size();
int is = 0, js = 0;
for (int i = 1; i < n; ++i) {
if(pt[i].y > pt[is].y) is = i;
if(pt[i].y < pt[js].y) js = i;
}
ll maxd = norm(pt[is]-pt[js]);
int i, maxi, j, maxj;
i = maxi = is;
j = maxj = js;
do {
if (cross((pt[(i+1)%pt.size()]-pt[i]), (pt[(j+1)%pt.size()]-pt[j])) >= 0) j = (j+1) % n;
else i = (i+1) % n;
if (norm(pt[i]-pt[j]) > maxd) {
maxd = norm(pt[i]-pt[j]);
maxi = i; maxj = j;
}
}while (i != is || j != js);
return maxd;
}
int main() {
int N;
cin >> N;
vector<int> X(N), Y(N);
rep(i, N)
scanf("%d%d", &X[i], &Y[i]);
if(N == 0) {
puts("1");
return 0;
}
unordered_map<int,int> a;
rep(i, N)
a.insert(mp(pack(Y[i],X[i]), i));
vector<bool> vis(N);
ll maxd = 0;
vector<P> points;
vi stk;
rep(s, N) if(!vis[s]) {
stk.clear();
points.clear();
stk.push_back(s);
vis[s] = true;
// cerr << s << ": " << endl;
while(!stk.empty()) {
int i = stk.back(); stk.pop_back();
int y0 = Y[i], x0 = X[i];
// cerr << "\t" << i << endl;
points.push_back(P(x0, y0));
rep(k, C) {
int y = y0 + circle[k][0], x = x0 + circle[k][1];
auto it = a.find(pack(y,x));
if(it != a.end()) {
int j = it->second;
if(!vis[j]) {
stk.push_back(j);
vis[j] = true;
}
}
}
}
if(points.size() >= 2) {
vector<P> ch = convex_hull(points);
ll d = convex_diameter(ch);
amax(maxd, d);
}
}
double ans = sqrt(maxd * 1.) + 2;
printf("%.10f\n", ans);
return 0;
}