C++ 解法, 执行用时: <1ms, 内存消耗: 0K, 提交时间: 2023-08-18 22:53:24

#include<bits/stdc++.h>
#define inf 1000000000000
#define M 100009
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
struct node
{
    double x,y;
    node(){}
    node(double xx,double yy)
    {
        x=xx;
        y=yy;
    }
    node operator -(node s)
    {
        return node(x-s.x,y-s.y);
    }
    node operator +(node s)
    {
        return node(x+s.x,y+s.y);
    }
    double operator *(node s)
    {
        return x*s.x+y*s.y;
    }
    double operator ^(node s)
    {
        return x*s.y-y*s.x;
    }
}p[M],a[M];
double max(double a,double b)
{
    return a>b?a:b;
}
double min(double a,double b)
{
    return a<b?a:b;
}
double len(node a)
{
    return sqrt(a*a);
}
double dis(node a,node b)//两点之间的距离
{
    return len(b-a);
}
double cross(node a,node b,node c)//叉乘
{
    return (b-a)^(c-a);
}
double dot(node a,node b,node c)//点乘
{
    return (b-a)*(c-a);
}
int judge(node a,node b,node c)//判断c是否在ab线段上（前提是c在直线ab上）
{
    if(c.x>=min(a.x,b.x)
       &&c.x<=max(a.x,b.x)
       &&c.y>=min(a.y,b.y)
       &&c.y<=max(a.y,b.y))
        return 1;
    return 0;
}
double area(node b,node c,double r)
{
    node a(0.0,0.0);
    if (dis(b,c)<eps) return 0.0;
    double h=fabs(cross(a,b,c))/dis(b,c);
    if(dis(a,b)>r-eps&&dis(a,c)>r-eps)//两个端点都在圆的外面则分为两种情况
    {
        double angle=acos(dot(a,b,c)/dis(a,b)/dis(a,c));
        if(h>r-eps)
        {
            return 0.5*r*r*angle;
        }
        else if(dot(b,a,c)>0&&dot(c,a,b)>0)
        {
            double angle1=2*acos(h/r);
            return 0.5*r*r*fabs(angle-angle1)+0.5*r*r*sin(angle1);
        }
        else
        {
            return 0.5*r*r*angle;
        }
    }
    else if(dis(a,b)<r+eps&&dis(a,c)<r+eps)//两个端点都在圆内的情况
    {
        return 0.5*fabs(cross(a,b,c));
    }
    else//一个端点在圆上一个端点在圆内的情况
    {
        if(dis(a,b)>dis(a,c))//默认b在圆内
        {
            swap(b,c);
        }
        if(fabs(dis(a,b))<eps)//ab距离为0直接返回0
        {
            return 0.0;
        }
        if(dot(b,a,c)<eps)
        {
            double angle1=acos(h/dis(a,b));
            double angle2=acos(h/r)-angle1;
            double angle3=acos(h/dis(a,c))-acos(h/r);
            return 0.5*dis(a,b)*r*sin(angle2)+0.5*r*r*angle3;

        }
        else
        {
            double angle1=acos(h/dis(a,b));
            double angle2=acos(h/r);
            double angle3=acos(h/dis(a,c))-angle2;
            return 0.5*r*dis(a,b)*sin(angle1+angle2)+0.5*r*r*angle3;
        }
    }
}
int n;
double x,y,h,x1,yy,R;
double gets(node O)//求圆与多边形面积并
{
    for (int i=1;i<=n+1;i++) p[i]=a[i];
      for(int i=1;i<=n+1;i++) p[i]=p[i]-O;
    O=node(0,0);
    double sum=0;
    for(int i=1;i<=n;i++)
    {
        int j=i+1;
        double s=area(p[i],p[j],R);
        if(cross(O,p[i],p[j])>0) sum+=s; else sum-=s;
    }
    return fabs(sum);
}
int dcmp(double x)
{
    if(x > eps) return 1;
    return x < -eps ? -1 : 0;
}
double calc(double x)
{
    double l=1000000,r=-100000,m1,m2,f1=0,f2=0;
    for (int i=1;i<=n;i++)
    {
        if (dcmp((a[i].x-x) * (a[i+1].x-x))<=0)
        {
            node tmp;
            tmp.x=a[i].x+(a[i+1].x-a[i].x)/(a[i+1].x-a[i].x)*(x-a[i].x);
            tmp.y=a[i].y+(a[i+1].y-a[i].y)/(a[i+1].x-a[i].x)*(x-a[i].x);
            l=min(l,tmp.y);
            r=max(r,tmp.y);
        }
    }
    while (l+eps<r)
    {
        m1=(l+l+r)/3.0;
        node bom=node(x,m1);
        f1=gets(bom);
        m2=(l+r+r)/3.0;
        bom=node(x,m2);
        f2=gets(bom);
        if (f1>f2) r=m2;else l=m1;
    }
    return f1;
}
int main()
{
    scanf("%d%lf",&n,&R);
    double l=1000,r=-1000,m1,m2,f1,f2;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a[i].x,&a[i].y);
        l=min(l,a[i].x);
        r=max(r,a[i].x);
    }
    a[n+1]=a[1];
    while (l+eps<r)
    {
        m1=(l+l+r)/3.0;f1=calc(m1);
        m2=(l+r+r)/3.0;f2=calc(m2);
        if (f1>f2) r=m2;else l=m1;
    }
    printf("%.6lf\n",f1);
    return 0;
}