出题人题解 | #Rabbit的蛋糕#

原题解链接：https://ac.nowcoder.com/discuss/151166

计算几何。

只要叉积维护一下前缀和就好了。

#include <cstdio>
#include <bits/stdc++.h>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)

typedef long long ll;
const int maxn = 200005;
const ll INF = 1e18;
const ll mod=1e9+7;
const double eps = 1e-9;

int n,m;

struct node
{
    double x,y;
}a[maxn];

double sum[maxn];

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

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    node zero;
    zero.x=0;
    zero.y=0;
    for(int i=1;i<=n;i++)
    {
        double ans=cross(zero,a[i],a[(i==n?1:i+1)]);
        sum[i]=sum[i-1]+ans;
    }
    for(int i=n+1;i<=2*n;i++)
    {
        sum[i]=sum[i-1]+sum[i-n];
    }
    double Sum=fabs(sum[n])/2.0;
    double cnt=0;
    for(int i=0;i<m;i++)
    {
        int ss,tt;
        scanf("%d%d",&ss,&tt);
        if(ss>tt) swap(ss,tt);
        double ans=sum[tt-1]-sum[ss-1];
        ans+=cross(zero,a[tt],a[ss]);
        ans=fabs(ans)/2.0;
        cnt=max(cnt,min(ans,Sum-ans));
    }
    printf("%.15f\n",cnt);
}