結果
| 問題 |
No.96 圏外です。
|
| コンテスト | |
| ユーザー |
 kosakkun
|
| 提出日時 | 2017-01-29 20:02:18 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,202 bytes |
| コンパイル時間 | 1,837 ms |
| コンパイル使用メモリ | 123,932 KB |
| 実行使用メモリ | 33,920 KB |
| 最終ジャッジ日時 | 2024-12-23 23:47:46 |
| 合計ジャッジ時間 | 79,488 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 12 WA * 8 TLE * 8 |
ソースコード
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
using namespace std;
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define FOREACH(i,Itr) for(auto (i)=(Itr).begin();(i)!=(Itr).end();(i)++)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
#define PB_VEC(Itr1,Itr2) (Itr1).insert((Itr1).end(),(Itr2).begin(),(Itr2).end())
#define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end())
#define LBOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val))
#define UBOUND(Itr,val) upper_bound((Itr).begin(),(Itr).end(),(val))
#define EPS 1.0e-8
#define MOD 1000000007
typedef long long ll;
struct Point {
double x,y;
Point(){}
Point(double _x, double _y):x(_x),y(_y){}
bool operator < (const Point &a) const {
return (x==a.x) ? (y<a.y) : (x<a.x);
}
};
Point operator +(const Point &a,const Point &b){return Point(a.x+b.x,a.y+b.y);}
Point operator -(const Point &a,const Point &b){return Point(a.x-b.x,a.y-b.y);}
Point operator *(const Point &a,double k){return Point(a.x*k,a.y*k);}
struct Segment {
Point p1,p2;
Segment(){}
Segment(Point _p1, Point _p2):p1(_p1),p2(_p2){}
Segment(double x1, double y1, double x2, double y2)
:p1(Point(x1,y1)),p2(Point(x2,y2)){}
};
struct Circle {
Point c; double r;
Circle(){}
Circle(Point _c, double _r):c(_c),r(_r){}
Circle(double x, double y, double _r):c(Point(x,y)),r(_r){}
};
typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;
double dot(Vector a, Vector b){return a.x*b.x + a.y*b.y;}
double cross(Vector a, Vector b){return a.x*b.y - a.y*b.x;}
double norm(Vector a){return sqrt(dot(a,a)*dot(a,a));}
Point Project(Segment s, Point p) {
Vector base = s.p2 - s.p1;
double r = dot(p - s.p1, base) / norm(base);
return s.p1 + base * r;
}
Point Reflect(Segment s, Point p) {
return p + (Project(s,p) - p) * 2.0;
}
double DistanceLinePoint(Line s, Point p) {
Vector dist = Project(s,p) - p;
return sqrt(norm(dist));
}
double DistanceSegmentPoint(Segment s, Point p) {
if(dot(s.p2 - s.p1, p -s.p1)<0.0)return sqrt(norm(p - s.p1));
if(dot(s.p1 - s.p2, p -s.p2)<0.0)return sqrt(norm(p - s.p2));
return DistanceLinePoint(s,p);
}
const int COUNTER_CLOCKWISE = 1;
const int CLOCKWISE = -1;
const int ONLINE_BACK = 2;
const int ONLINE_FRONT = -2;
const int ON_SEGMENT = 0;
int CounterClockwise(Point p0, Point p1, Point p2) {
Vector a = p1 - p0;
Vector b = p2 - p0;
if(cross(a,b)>1.0e-8)return COUNTER_CLOCKWISE;
if(cross(a,b)<-1.0e-8)return CLOCKWISE;
if(dot(a,b)<-1.0e-8)return ONLINE_BACK;
if(norm(a)<norm(b))return ONLINE_FRONT;
return ON_SEGMENT;
}
bool Intersect(Point p1, Point p2, Point p3, Point p4) {
return (CounterClockwise(p1,p2,p3) * CounterClockwise(p1,p2,p4) <= 0 &&
CounterClockwise(p3,p4,p1) * CounterClockwise(p3,p4,p2) <= 0);
}
bool Intersect(Segment s1, Segment s2) {
return Intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}
Point CrossPoint(Segment s1, Segment s2){
Vector base = s2.p2 - s2.p1;
double d1 = abs(cross(base,s1.p1 - s2.p1));
double d2 = abs(cross(base,s1.p2 - s2.p1));
double t = d1 / (d1+d2);
return s1.p1 + (s1.p2-s1.p1) * t;
}
Polygon ConvexHull(vector<Point> pos) {
int n = (int)pos.size(), k = 0;
sort(pos.begin(),pos.end());
Polygon ch(2*n);
for(int i=0;i<n;ch[k++]=pos[i++])
while(k>=2 && CounterClockwise(ch[k-2],ch[k-1],pos[i])<=0)--k;
for(int i=n-2,t=k+1;i>=0;ch[k++]=pos[i--])
while(k>=t && CounterClockwise(ch[k-2],ch[k-1],pos[i])<=0)--k;
ch.resize(k-1);
return ch;
}
double ConvexDiameter(Polygon &pos) {
int n = (int)pos.size();
int is = 0, js = 0;
for(int i=1;i<n;++i) {
if (pos[i].y > pos[is].y) is = i;
if (pos[i].y < pos[js].y) js = i;
}
double maxd = norm(pos[is]-pos[js]);
int i, maxi, j, maxj;
i = maxi = is;
j = maxj = js;
do{
if(cross(pos[(i+1)%n]-pos[i],pos[(j+1)%n]-pos[j])>=0)j=(j+1)%n;
else i=(i+1)%n;
if(norm(pos[i]-pos[j]) > maxd) {
maxd = norm(pos[i]-pos[j]);
maxi = i; maxj = j;
}
}while(i!=is || j!=js);
return sqrt(maxd);
}
class UnionFind {
vector<int> data;
public:
UnionFind(int size) : data(size, -1) { }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
int size(int x) {
return -data[root(x)];
}
};
int main(){
int N; cin>>N;
vector<Point> p(N);
REP(i,N)cin>>p[i].x>>p[i].y;
map<Point,int> v;
REP(i,N)v[p[i]]=i;
UnionFind inst(120010);
REP(kai,N){
for(double i=-10.0;i<=10.0;i+=1.0){
for(double j=-10.0;j<=10.0;j+=1.0){
Point pt(p[kai].x+i,p[kai].y+j);
if(sqrt(i*i+j*j)+EPS<=10.0){
if(v.find(pt)!=v.end()){
inst.unionSet(v[pt],v[p[kai]]);
}
}
}
}
}
map<int,vector<int>> forest;
REP(i,p.size())forest[inst.root(v[p[i]])].push_back(v[p[i]]);
double ans = 0;
FOREACH(kai,forest){
vector<int> f = kai->second;
vector<Point> pol(f.size());
REP(i,f.size())pol[i]=p[f[i]];
if(pol.size()==2){
Vector vt = pol[0] - pol[1];
ans = max(sqrt(norm(vt)),ans);
}else if(pol.size()>=3){
Polygon pt = ConvexHull(pol);
ans = max(ans,ConvexDiameter(pt));
}
}
cout<<fixed<<setprecision(10)<<ans+2.0<<endl;
return 0;
}