結果

問題 No.96 圏外です。
ユーザー koyumeishi
提出日時 2014-12-07 22:47:01
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 428 ms / 5,000 ms
コード長 5,617 bytes
コンパイル時間 1,545 ms
コンパイル使用メモリ 110,016 KB
実行使用メモリ 22,580 KB
最終ジャッジ日時 2024-12-24 07:48:14
合計ジャッジ時間 6,087 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define EPS 1e-6
class xy{
    
public:
    double x;
    double y;
    xy(){
    }
    
    xy(double xx, double yy){
        x = xx;
        y = yy;
    }
    xy(const xy &v){
        x = v.x;
        y = v.y;
    }
    xy& operator=(const xy &v){
        x = v.x;
        y = v.y;
        return *this;
    }
    xy operator+(const xy &v) const{
        return xy(this->x+v.x, this->y+v.y);
        
    }
    
    xy operator-(const xy &v) const{
        return xy(this->x-v.x, this->y-v.y);
    }
    
    void operator+=(const xy &v){
        x+=v.x;
        y+=v.y;
    }
    void operator-=(const xy &v){
        x-=v.x;
        y-=v.y;
    }
/* something wrong this operator for sorting
    bool operator<(const xy &v){
        if(x!=v.x) return x < v.x;
        return y < v.y;
    }
    bool operator>(const xy &v){
        if(x!=v.x) return x > v.x;
        return y > v.y;
    }
*/
};
//for sorting
bool comp_xy(const xy &a, const xy &b){
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
//u,v : vector O = (0,0)
double cross(const xy &u, const xy &v){
    return u.x*v.y - u.y*v.x;
}
//u,v : vector O = (0,0)
double dot(const xy &u, const xy &v){
    return u.x*v.x + u.y*v.y;
}
//distance between two points
double dist_p_p(const xy &a, const xy &b){
    return sqrt( fabs(dot(a-b, a-b)) );
}
//distance between a point and a line segment
double dist_p_ls(const xy &p, const xy &s1, const xy &s2){
    xy vl = s2 - s1;
    xy vp = p - s1;
    return fabs( cross(vl, vp) / sqrt( dot(vl, vl) ) );
}
//zero -> p1
int ccw(xy p1, xy p2, xy p3){
    p2 -= p1;
    p3 -= p1;
    double c = cross(p2,p3);
    if( c > EPS /* c > 0 */) return +1;         //counter-clockwise
    if( c < -EPS /* c < 0 */) return -1;        //clock-wise
    if( dot(p2,p3) < -EPS) return +2;           //on segment : p3-p1-p2
    if( dot(p3,p3) < dot(p2,p2) +EPS ) return -2;   //on segment : p1-p3-p2
    return 0;
}
//segment p1-p2, p3-p4
bool inter_ss(xy p1, xy p2, xy p3, xy p4){
    return ( (ccw(p1,p2, p3) * ccw(p1,p2, p4) <= 0) && (ccw(p3,p4, p1) * ccw(p3,p4, p2) <= 0 ) ) ;
}
//convex_hull
vector<xy> convex_hull(vector<xy> &v){
    sort( v.begin(), v.end(), comp_xy );
    int k = 0;  //nums of vertex
    vector<xy> tmp(v.size()*2);
    //conect i from k
    for(int i=0; i<v.size(); i++){
        while(k>1 && cross (tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--;
        tmp[k] = v[i];
        k++;
    }
    
    for(int i=v.size()-2, t=k; i>=0; i--){
        while(k>t && cross(tmp[k-1] - tmp[k-2], v[i] - tmp[k-1]) <= 0 ) k--;
        tmp[k] = v[i];
        k++;
    }
    tmp.resize(k-1);
    return tmp;
}
pair<int, int> farthest_point_pair(vector<xy> &v /* v MUST BE CONVEX HULL*/){
    int n = v.size();
    
    int p = 0;  //the point which has min y
    int q = 0;  //the point which has max y
    for(int i=0; i<n; i++){
        if( v[p].y > v[i].y ) p = i;
        if( v[q].y < v[i].y ) q = i;
    }
    double max_dist = dist_p_p( v[p], v[q] );
    int ret_a = p;
    int ret_b = q;
    
    int s = p;
    int t = q;
    while(1){
        if( cross( v[(s+1)%n]-v[s], v[(t+1)%n] - v[t] ) < 0 ) s = (s+1)%n;
        else t = (t+1)%n;
        if( dist_p_p( v[s], v[t] ) > max_dist ){
            ret_a = s;
            ret_b = t;
            max_dist = dist_p_p( v[s], v[t] );
        }
        
        if( s==p && t==q ) break;
    }
    return make_pair(ret_a, ret_b);
}
class UnionFindTree{
    typedef struct {
        int parent;
        int rank;
    }base_node;
    
    vector<base_node> node;
public:
    UnionFindTree(int n){
        node.resize(n);
        for(int i=0; i<n; i++){
            node[i].parent=i;
            node[i].rank=0;
        }
    }
    int find(int x){
        if(node[x].parent == x) return x;
        else{
            return node[x].parent = find(node[x].parent);
        }
    }
    
    bool same(int x, int y){
        return find(x) == find(y);
    }
    void unite(int x, int y){
        x = find(node[x].parent);
        y = find(node[y].parent);
        if(x==y) return;
        if(node[x].rank < node[y].rank){
            node[x].parent = y;
        }else if(node[x].rank > node[y].rank){
            node[y].parent = x;
        }else{
            node[x].rank++;
            unite(x,y);
        }
    }
};
bool check(xy &a, xy &b){
    return dist_p_p(a,b) <= 10;
}
int main(){
    int n;
    cin >> n;
    vector<pair<int,int> > events(n*2);
    vector<int> Y(n);
    vector<xy> q(n);
    for(int i=0; i<n; i++){
        int x,y;
        cin >> x >> y;
        Y[i] = y;
        
        events.push_back( make_pair(x-10, i) );
        events.push_back( make_pair(x+10, n+i) );
        
        q[i] = xy(x,y);
    }
    sort(events.begin(), events.end());
    
    UnionFindTree uft(n);
    set< pair<int, int> > my_list;
    for(int i=0; i<events.size(); i++){
        int id = events[i].second;
        if(id < n){
            auto begin = my_list.lower_bound( make_pair( Y[id]-15, id) );
            
            auto end = my_list.upper_bound(make_pair( Y[id]+15, id ) );
            
            for(auto itr = begin; itr!=end; itr++){
                if( check(q[id], q[ itr->second ]) ){
                    uft.unite(id, itr->second );
                }
            }
            my_list.insert( make_pair( Y[id], id ) );
        }else{
            my_list.erase( make_pair( Y[id-n], id-n ) );
        }
    }
    map<int, vector<xy> > S;
    for(int i=0; i<n; i++){
        int par = uft.find(i);
        if(S.find(par) != S.end()){
            S[par].push_back( q[i] );
        }else{
            S[par] = vector<xy>(0);
            S[par].push_back( q[i] );
        }
    }
    
    double ans = 1.0;
    for(auto itr = S.begin(); itr != S.end(); itr++){
        if(itr->second.size() == 1){
            ans = max(ans, 2.0);
            continue;
        }
        
        vector<xy> hull = convex_hull( itr->second );
        
        
        pair<int,int> d = farthest_point_pair(hull);
        double tmp = dist_p_p( hull[d.first], hull[d.second] ) + 2.0;
        ans = max(ans, tmp);
    }
    printf("%.7f\n", ans);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0