#146865 (C++14) No.96 圏外です。

提出ソース

結果

問題	No.96 圏外です。
ユーザー	kosakkun
提出日時	2017-01-29 20:02:18
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,202 bytes
コンパイル時間	1,656 ms
コンパイル使用メモリ	123,940 KB
実行使用メモリ	18,204 KB
最終ジャッジ日時	2024-06-06 09:31:50
合計ジャッジ時間	13,387 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	AC	50 ms 6,940 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	AC	254 ms 6,940 KB
testcase_08	AC	374 ms 6,944 KB
testcase_09	AC	535 ms 7,552 KB
testcase_10	AC	731 ms 8,064 KB
testcase_11	WA	-
testcase_12	AC	1,276 ms 12,160 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	--	-

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

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード