BZOJ1069【SCOI2007】最大土地面积 <旋转卡壳>

Problem

【SCOI2007】最大土地面积

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

在某块平面土地上有$N$个点，你可以选择其中的任意四个点，使得这四个点围成的土地面积最大。

Input

第$1$行一个正整数$N$，接下来$N$行，每行$2$个数$x,y$，表示该点的横坐标和纵坐标。

Output

最大的多边形面积，答案精确到小数点后$3$位。

Sample Input

5
0 0
1 0
1 1
0 1
0.5 0.5

Sample Output

1.000

HINT

数据范围: $n\le 2000$，$|x|,|y|\le 10^5$

标签：旋转卡壳

Solution

基础旋转卡壳。

首先这四个点一定在凸包上，先求凸包。

考虑枚举每条对角线，找出其两边最远的点，即可找到该对角线对应的最大四边形。
这样就是一个$O(n^3)$的暴力。

枚举对角线的一段，移动另一端，发现两边最远的点都是单调移动的，于是可以带上旋转卡壳，这样内层循环的总复杂度时$O(n)$，就有了一个$O(n^2)$的优质算法。

Code

#include <bits/stdc++.h>
#define MAX_N 2000
using namespace std;
typedef double dnt;
int n, m;
struct pnt {
    dnt x, y;
    dnt operator * (const pnt &t) const {return x*t.y-y*t.x;}
    pnt operator - (const pnt &t) const {return (pnt){x-t.x, y-t.y};}
    bool operator < (const pnt &t) const {return x == t.x ? y < t.y : x < t.x;}
} p[MAX_N+5], c[MAX_N*2+5], mat[MAX_N*2+5][2];
dnt S(pnt a, pnt b, pnt c, pnt d) {return (a*b+b*c+c*d+d*a)/2;}
void ConvexHull() {
    sort(p+1, p+n+1), c[++m] = p[1], c[++m] = p[2];
    for (int i = 3; i <= n; c[++m] = p[i++])
        while (m > 1 && (p[i]-c[m-1])*(c[m]-c[m-1]) >= 0) m--;
    int t = m;	c[++m] = p[n-1];
    for (int i = n-2; i; c[++m] = p[i--])
        while (m > t && (p[i]-c[m-1])*(c[m]-c[m-1]) >= 0) m--;
    m--;	for (int i = 1; i <= m; i++) c[i+m] = c[i];
}
dnt RotatingCalipers() {
    dnt ret = 0;
    if (m == 3) return (c[1]*c[2]+c[2]*c[3]+c[3]*c[1])/2;
    for (int i = 1; i <= m; i++) {
        for (int j = i+2, t = j-1; j <= i+m-2; j++)
            {while (t < j && (c[t+1]-c[t])*(c[j]-c[i]) >= 0) t++;	mat[j][0] = c[t];}
        for (int j = i+m-2, t = j+1; j >= i+2; j--)
            {while (t > j && (c[t-1]-c[t])*(c[j]-c[i]) <= 0) t--;	mat[j][1] = c[t];}
        for (int j = i+2; j <= i+m-2; j++) ret = max(ret, S(c[i], mat[j][0], c[j], mat[j][1]));
    }
    return ret;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
    return ConvexHull(), printf("%.3lf", RotatingCalipers()), 0;
}