题解 P4166 【[SCOI2007]最大土地面积】

SuperJvRuo

2018-01-29 16:28:38

Solution

一道很有意思的计算几何 四边形的四个顶点显然一定在凸包上 那么求出凸包之后呢?我们很容易想到枚举四个顶点的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; } ```