FJ集训2015 签到题（旋转卡壳）

发表于 |
字数统计: 598字 | 阅读时长 ≈ 3min

【FJ集训2015】签到题

问题描述
给定一个n个点的严格凸多边形（各个内角<180°），现在要切出两个非退化三角形（三点不共线），要求两个三角形顶点必须是凸多边形的顶点，且三角形不可相交（但是点或边可以重合）。求两个三角形面积之差的最大值。

输入格式
第一行，一个整数N。

第二到N+1行，每行两个整数xi,yi，表示多边形的一个点，保证顶点按顺时针或逆时针顺序给出。

输出格式
输出答案，精确到小数点后1位。

样例输入 1

4

0 0

0 1

1 2

1 0

样例输出 1

0.5

样例输入 2

5

0 0

-1 6

0 7

2 8

7 7

样例输出 2

24.0

提示

对于15%的数据，$N<=10$

对于45%的数据，$N<=307$

对于100%的数据，$4<=N<=5000， 0<=|xi|,|yi|<=10^8$

为了使面积之差最大，我们考虑枚举面积较大的一个三角形，那么当该三角形确定的时候，容易发现此时面积最小的三角形一定是三个相邻的顶点构成的，因此只需要在旋转卡壳的时候记录一下底边下面的三角形最小面积就行了。卡完一圈就能算出答案了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 10005
#define ll long long
using namespace std;
struct node{ll x,y;}P[N];
node operator+(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator-(node a,node b){return (node){a.x-b.x,a.y-b.y};}
ll operator*(node a,node b){return a.x*b.y-a.y*b.x;}
ll n,Ans=-9e18;
ll Area(ll i,ll j,ll k)
{
	node w=P[j]-P[i],v=P[k]-P[i];
	return abs(w*v);
}
int main()
{
	ll i,j,k,x,y,Max,Min;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x,&y);
		P[i]=(node){x,y};P[n+i]=P[i];
	}
	P[0]=P[n];
	for(i=1;i<=n;i++)
	for(j=i+2,k=i+3,Min=9e18;j<i+n&&k<i+n;j++)
	{
		while(k<i+n-1&&Area(k+1,i,j)>=Area(k,i,j))k++;
		Min=min(Min,Area(j,j-1,j-2));
		Max=Area(i,j,k);Ans=max(Ans,Max-Min);
	}
	if(Ans&1)printf("%lld.5",Ans>>1);
	else printf("%lld.0",Ans>>1);
}