제출 #1304216

#제출 시각아이디문제언어결과실행 시간메모리
1304216liptonek두 개의 원 (balkan11_2circles)C++20
100 / 100
925 ms19844 KiB
#include <bits/stdc++.h>
using namespace std;

struct Point 
{
    long double x, y;
};

struct Line 
{
    Point p1, p2;

    long double angle;
    
    Line() {}

    Line(Point a, Point b) : p1(a), p2(b) 
    {
        angle=atan2l(b.y-a.y, b.x-a.x);
    }
};

long double cross(Point a, Point b, Point c) 
{
    return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

Point intersect(Line l1, Line l2) 
{
    long double a1=l1.p2.y-l1.p1.y;
    long double b1=l1.p1.x-l1.p2.x;
    long double c1=-(a1*l1.p1.x+b1*l1.p1.y);
    
    long double a2=l2.p2.y-l2.p1.y;
    long double b2=l2.p1.x-l2.p2.x;
    long double c2=-(a2*l2.p1.x+b2*l2.p1.y);
    
    long double det=a1*b2-a2*b1;

    return {(b1*c2-b2*c1)/det,(a2*c1-a1*c2)/det};
}

bool outside(Line l, Point p) 
{
    return cross(l.p1, l.p2, p)<-1e-10; 
}

vector<Point> half_planes(vector<Line>& lines) 
{
    int n=lines.size();

    if(n==0) 
    {
        return {};
    }
    
    int start=0;

    for(int i=1; i<n; i++) 
    {
        if(lines[i].angle<lines[start].angle) 
        {
            start=i;
        }
    }

    vector<Line> sorted;

    for(int i=0; i<n; i++) 
    {
        sorted.push_back(lines[(start+i)%n]);
    }
    
    vector<Line> unique_lines;
    
    for(int i=0; i<n; i++) 
    {
        if(!unique_lines.empty() && fabsl(sorted[i].angle-unique_lines.back().angle)<1e-13) 
        {
            if(outside(unique_lines.back(), sorted[i].p1)) 
            {
                unique_lines.back()=sorted[i];
            }

            continue;
        }

        unique_lines.push_back(sorted[i]);
    }
    
    deque<Line> dq;

    for(int i=0; i<(int)unique_lines.size(); i++) 
    {
        while(dq.size()>1 && outside(unique_lines[i], intersect(dq[dq.size()-1], dq[dq.size()-2]))) 
        {
            dq.pop_back();
        }

        while(dq.size()>1 && outside(unique_lines[i], intersect(dq[0], dq[1]))) 
        {
            dq.pop_front();
        }

        dq.push_back(unique_lines[i]);
    }

    while(dq.size()>2 && outside(dq[0], intersect(dq[dq.size()-1], dq[dq.size()-2]))) 
    {
        dq.pop_back();
    }

    while(dq.size()>2 && outside(dq[dq.size()-1], intersect(dq[0], dq[1]))) 
    {
        dq.pop_front();
    }
    
    if(dq.size()<3) 
    {
        return {};
    }

    vector<Point> res;

    for(int i=0; i<(int)dq.size(); i++) 
    {
        res.push_back(intersect(dq[i], dq[(i+1)%dq.size()]));
    }

    return res;
}

long double dist(Point a, Point b) 
{
    return(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

long double diameter(const vector<Point>& poly) 
{
    int n=poly.size();

    if(n<2) 
    {
        return 0;
    }

    if(n==2) 
    {
        return sqrtl(dist(poly[0], poly[1]));
    }

    long double d=0;
    int k=1;

    for(int i=0; i<n; i++) 
    {
        while(fabsl(cross(poly[i], poly[(i+1)%n], poly[(k+1)%n]))>fabsl(cross(poly[i], poly[(i+1)%n], poly[k]))) 
        {
            k=(k+1)%n;
        }

        d=max(d, sqrtl(dist(poly[i], poly[k])));
        d=max(d, sqrtl(dist(poly[(i+1)%n], poly[k])));
    }

    return d;
}

bool fit(long double R, int N, const vector<Point>& pts) 
{
    vector<Line> shifted;

    for(int i=0; i<N; i++) 
    {
        Point p1=pts[i];
        Point p2=pts[(i+1)%N];

        long double dx=p2.x-p1.x, dy=p2.y-p1.y;
        long double len=sqrtl(dx*dx+dy*dy);
        
        if(len<1e-10) 
        {
            continue;
        }
        
        long double nx=-dy/len, ny=dx/len; 
        
        shifted.push_back(Line({p1.x+R*nx, p1.y+R*ny}, {p2.x+R*nx, p2.y+R*ny}));
    }

    vector<Point> inner=half_planes(shifted);
    
    return diameter(inner)>=2.0*R;
}

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N;
    cin>>N;

    vector<Point> pts(N);
    
    for(int i=0; i<N; i++) 
    {
        cin>>pts[i].x>>pts[i].y;
    }
    
    long double low=0;
    long double high=2e7;

    for(int iter=0; iter<80; iter++) 
    {
        long double mid=(low+high)/2.0;

        if(fit(mid, N, pts)) 
        {
            low=mid;
        }
        else 
        {
            high=mid;
        }
    }
    
    cout<<fixed<<setprecision(3)<<(double)low<<endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...