Submission #1214839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214839		biank	두 개의 원 (balkan11_2circles)	C++20	100 / 100	229 ms	9016 KiB

twocircles

#include <bits/stdc++.h>

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;

const ld EPS=1e-6;
const ld INF=1e8;

struct pt{
    ld x,y;
    friend pt operator+(pt a, pt b){
        return pt{a.x+b.x,a.y+b.y};
    }
    friend pt operator-(pt a, pt b){
        return pt{a.x-b.x,a.y-b.y};
    }
    ld abs2(){
        return x*x+y*y;
    }
    ld abs(){
        return sqrt(abs2());
    }
    pt perp(){
        return pt{-y,x};
    }
    friend ld operator*(pt a, pt b){
        return a.x*b.x+a.y*b.y;
    }
    friend ld operator^(pt a, pt b){
        return a.x*b.y-a.y*b.x;
    }
    friend pt operator*(ld k, pt a){
        return pt{k*a.x,k*a.y};
    }
};

struct line{
    pt p,d;
    line(){}
    line(pt a, pt b){
        p=a;
        d=b-a;
    }
    bool out(pt r){
        return (d^(r-p))<-EPS; 
    }
    friend pt inter(line s, line t){
        ld alpha=((t.p-s.p)^t.d)/(s.d^t.d);
        return s.p+alpha*s.d;
    }
};

vector<pt> hp_intersect(vector<line> &h){
    deque<line> dq;
    forn(i,sz(h)){
        while(sz(dq)>=2&&h[i].out(inter(dq[sz(dq)-1],dq[sz(dq)-2]))) dq.pop_back();
        while(sz(dq)>=2&&h[i].out(inter(dq[0],dq[1]))) dq.pop_front();
        if(!empty(dq)&&fabs(h[i].d^dq.back().d)<EPS){
            if(h[i].d*dq.back().d<0.0) return vector<pt>{};
            if(h[i].out(dq.back().p)) dq.pop_back();
            else continue;
        }
        dq.pb(h[i]);
    }
    while(sz(dq)>=3&&dq[0].out(inter(dq[sz(dq)-1],dq[sz(dq)-2]))) dq.pop_back();
    while(sz(dq)>=3&&dq[sz(dq)-1].out(inter(dq[0],dq[1]))) dq.pop_front();
    if(sz(dq)<3) return vector<pt>{};
    vector<pt> p(sz(dq));
    forn(i,sz(dq)) p[i]=inter(dq[i],dq[(i+1)%sz(dq)]);
    return p;
}

ld max_dist(vector<pt> &p){
    ld maxi=0.0;
    int n=sz(p);
    int j=1;
    forn(i,n){
        pt a=p[i],b=p[(i+1)%n];
        while(((b-a)^(p[j]-a))<((b-a)^(p[(j+1)%n]-a))) j=(j+1)%n;
        maxi=max(maxi,(a-p[j]).abs());
        maxi=max(maxi,(b-p[j]).abs());
    }
    return maxi;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin>>n;
    vector<pt> p(n);
    forn(i,n) cin>>p[i].x>>p[i].y;
    
    auto check=[&](ld r){
        vector<line> h(n);
        forn(i,n){
            pt dir=(p[(i+1)%n]-p[i]).perp();
            dir=r/dir.abs()*dir;
            h[i]={p[i]+dir,p[(i+1)%n]+dir};
        }
        vector<pt> poly=hp_intersect(h);
        return max_dist(poly)>=2*r;
    };
    
    ld lo=0,hi=INF;
    while(hi-lo>EPS){
        ld mid=(lo+hi)/2;
        if(check(mid)) lo=mid;
        else hi=mid;
    }
    cout<<fixed<<setprecision(10)<<lo<<'\n';
    
    return 0;
}

• Subtask 1: 100 / 100