C++14(g++5.4) 解法, 执行用时: 117ms, 内存消耗: 2280K, 提交时间: 2019-01-04 20:26:03

#include<bits/stdc++.h>
#define db double
using namespace std;
const int maxn=1e5+10;
db x[maxn],y[maxn],sum1[maxn],sum2[maxn],ans;
int main()
{
	int n,q,s,t;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	scanf("%lf%lf",&x[i],&y[i]);

	y[n+1]=y[1],x[n+1]=x[1];
	for(int i=1;i<=n;i++)
	{
		sum1[i]=sum1[i-1]+x[i]*y[i+1];
		sum2[i]=sum2[i-1]+y[i]*x[i+1];
	}
	db S=(sum1[n]-sum2[n])/2;
	while(q--)
	{
		scanf("%d%d",&s,&t);
		if(s>t)swap(s,t);
		db t1=sum1[t-1]-sum1[s-1]+x[t]*y[s];
		db t2=sum2[t-1]-sum2[s-1]+y[t]*x[s];
		db tmp=(t1-t2)/2;
		ans=max(ans,min(tmp,S-tmp));
	}
	printf("%.2lf\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 83ms, 内存消耗: 2424K, 提交时间: 2019-01-04 22:15:27

#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
using namespace std;
const int N=1e5+5;
int n,m; double sum[N],ans;
struct P{
	double x,y; P(double x=0,double y=0):x(x),y(y){}
	double det(P t){return x*t.y-y*t.x;}
}a[N];
int main(){
	scanf("%d%d",&n,&m);
	rep (i,1,n) scanf("%lf%lf",&a[i].x,&a[i].y); a[n+1]=a[1];
	rep (i,1,n) sum[i]=sum[i-1]+a[i].det(a[i+1]);
	while (m--){
		int x,y; scanf("%d%d",&x,&y);
		if (x>y) swap(x,y);
		double t=sum[y-1]-sum[x-1]-a[x].det(a[y]);
		ans=max(min(t,sum[n]-t),ans);
	}
	printf("%lf\n",ans/2);
	return 0;
}