题解 P4166 【[SCOI2007]最大土地面积】
SuperJvRuo
2018-01-29 16:28:38
一道很有意思的计算几何
四边形的四个顶点显然一定在凸包上
那么求出凸包之后呢?我们很容易想到枚举四个顶点的O(n^4)的做法
但是如果用旋(xuán)转(zhuǎn)卡(qiǎ)壳(ké)来优化的话
![](https://cdn.luogu.com.cn/upload/pic/13682.png )
就变成了O(n^2)
```cpp
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct Point
{
double x, y;
}point[2018], stack[2018];
int n, top;
double ans;
//各种向量运算
double dis(Point a, Point b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
Point operator - (Point a, Point b)
{
return (Point){a.x - b.x, a.y - b.y};
}
double operator * (Point a, Point b)
{
//向量叉积cross(A,B)=xA*yB-xB*yA;
return a.x * b.y - a.y * b.x;
}
bool operator < (Point a, Point b)
{
double t = (a - point[1]) * (b - point[1]);
return t > 0 || t == 0 && dis(point[1], a) < dis(point[1], b);
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%lf%lf", &point[i].x, &point[i].y);
//求凸包
//迭代找出纵坐标最小的点
int k = 1;
for(int i = 2; i <= n; i++)
if(point[k].y > point[i].y || point[k].y == point[i].y && point[k].x > point[i].x)
k = i;
swap(point[k], point[1]);
//按极角排序
sort(point + 2, point + n + 1);
//我们钦定纵坐标最小的点、极角最小的点一定在凸包上
stack[++top] = point[1]; stack[++top] = point[2];
for(int i = 3; i <= n; i++)
{
while(top > 1 && (stack[top] - stack[top-1]) * (point[i] - stack[top-1]) <= 0)
//叉积小于0,说明栈顶向量不在凸包上
top--;
stack[++top] = point[i];
//新向量加入凸包
}
//旋转卡壳
stack[top+1] = point[1];
int a, b;
for(int i = 1; i <= top; i++)
{
a = i % top + 1; b = (i + 2) % top + 1;
for(int j = i + 2; j <= top; j++)
{
while(a % top + 1 != j && (stack[a] - stack[i])*(stack[j] - stack[i]) < (stack[a+1] - stack[i])*(stack[j] - stack[i]))
a = a % top + 1;
while(b % top + 1 != j && (stack[j] - stack[i])*(stack[b] - stack[i]) < (stack[j] - stack[i])*(stack[b+1] - stack[i]))
b = b % top + 1;
ans = max(ans, (stack[a] - stack[i])*(stack[j] - stack[i]) + (stack[j] - stack[i])*(stack[b] - stack[i]));
}
}
printf("%.3lf",ans/2.0);
return 0;
}
```