結果

問題 No.96 圏外です。
ユーザー kosakkunkosakkun
提出日時 2017-01-29 20:02:18
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,202 bytes
コンパイル時間 1,841 ms
コンパイル使用メモリ 120,876 KB
実行使用メモリ 12,084 KB
最終ジャッジ日時 2023-08-25 15:09:52
合計ジャッジ時間 14,755 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
8,760 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 52 ms
4,380 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 267 ms
5,716 KB
testcase_08 AC 396 ms
6,536 KB
testcase_09 AC 571 ms
7,524 KB
testcase_10 AC 809 ms
7,860 KB
testcase_11 WA -
testcase_12 AC 1,438 ms
12,084 KB
testcase_13 TLE -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0