https://ac.nowcoder.com/acm/contest/328/F

C++版本一

题解：计算几何裸题

参考文章：https://blog.csdn.net/weixin_43272781/article/details/85800560

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
double ans;
struct node{
    double x,y;


}e[N];
double a[N];
char str;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d%d",&n,&q);
    if(n==3){
        printf("%.6f",ans);
        return 0;
    }
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&e[i].x,&e[i].y);
    }
    for(int i=1;i<=n;i++){
        if(n==1)
        a[i]=a[i-1]+e[i].y*e[n].x-e[i].x*e[n].y;
        else
        a[i]=a[i-1]+e[i].y*e[i-1].x-e[i].x*e[i-1].y;
    }
    double sum=fabs(a[n]/2);
    //cout<<sum<<endl;
    int s,t;
    while(q--){
        scanf("%d%d",&s,&t);

        if(s>t)
            swap(s,t);
        if(abs(s-t)==1||s==1&&t==n)
            continue;
        double sumtmp=fabs((a[t]-a[s]+e[s].y*e[t].x-e[s].x*e[t].y)/2);
        ans=max(ans,min(sumtmp,sum-sumtmp));
    }
    printf("%.6f",ans);
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：

计算几何
只要叉积维护一下前缀和就好了。

#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);
}