Chlience

【题解】BZOJ 1069 [SCOI2007]最大土地面积
Problem给定平面上 $n$ 个点,求最大的四边形面积Thought旋转卡壳入门题可以证明四个点必然在凸包上然...
扫描右侧二维码阅读全文
21
2019/01

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

Problem

给定平面上 $n$ 个点,求最大的四边形面积

Thought

旋转卡壳入门题

可以证明四个点必然在凸包上
然后我们枚举一条对角线上的两个点,然后做旋转卡壳

旋转卡壳模板来自于 boshi (你咋比别人就是长些呢?
也就是找两侧面积最大的三角形
注意算的是有向面积防止两点出现在同一侧

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
struct Vector {
    double x, y;
    Vector operator + (const Vector a) const {return Vector{x + a.x, y + a.y};}
    Vector operator - (const Vector a) const {return Vector{x - a.x, y - a.y};}
    Vector operator * (const double a) const {return Vector{x * a, y * a};}
    double operator * (const Vector a) const {return x * a.y - y * a.x;}
}v[N], sta[N];
int n, top;
bool cmp1(Vector, Vector);
bool cmp2(Vector, Vector);
void graham();
double rotatingCalipers();
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i)
        scanf("%lf %lf", &v[i].x, &v[i].y);
    graham();
    printf("%.3f\n", rotatingCalipers());
    return 0;
}
bool cmp1(Vector a, Vector b) {
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
bool cmp2(Vector a, Vector b) {
    double p = (a - v[0]) * (b - v[0]);
    if(p == 0) return a.x < b.x;
    return p > 0;
}
void graham() {
    sort(v, v + n, cmp1);
    sort(v + 1, v + n, cmp2);
    for(int i = 0; i < n; ++ i) {
        while(top >= 2 && (v[i] - sta[top]) * (sta[top] - sta[top - 1]) >= 0) -- top;
        sta[++ top] = v[i];
    }
}
double rotatingCalipers() {
    double ans = 0;
    for(int i = 1; i <= top; ++ i) {
        int p = i % top + 1;
        int a = i, b = i;
        for(int j = i + 1; j <= top; ++ j) {
            while((sta[a % top + 1] - sta[i]) * (sta[p] - sta[i]) > (sta[a] - sta[i]) * (sta[p] - sta[i])) a = a % top + 1;
            while((sta[(a + top - 2) % top + 1] - sta[i]) * (sta[p] - sta[i]) > (sta[a] - sta[i]) * (sta[p] - sta[i])) a = (a + top - 2) % top + 1;
            while((sta[(b + top - 2) % top + 1] - sta[i]) * (sta[p] - sta[i]) < (sta[b] - sta[i]) * (sta[p] - sta[i])) b = (b + top - 2) % top + 1;
            while((sta[b % top + 1] - sta[i]) * (sta[p] - sta[i]) < (sta[b] - sta[i]) * (sta[p] - sta[i])) b = b % top + 1;
            ans = max(ans, (sta[a] - sta[i]) * (sta[p] - sta[i]) - (sta[b] - sta[i]) * (sta[p] - sta[i]));
            p = p % top + 1;
        }
    }
    return ans / 2;
}
Last modification:January 21st, 2019 at 08:44 pm

Leave a Comment