卧薪尝胆,厚积薄发。
SCOI2007 最大土地面积
Date: Sun Dec 09 14:21:17 CST 2018 In Category: NoCategory

Description:

平面上有 $N$ 个点,选择其中的任意四个点围成的多边形面积最大。
$1\leqslant n\leqslant 2000$

Solution:

可以 $O(n^2)$ 枚举相对的点,然后同时旋转卡壳,维护两个双指针,分别是两边的点。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;
int n;
#define MAXN 4010
struct point
{
double x,y;
}p[MAXN];
bool cmp_x(point a,point b){return a.x < b.x;}
bool equal(double a,double b){return (fabs(a - b) <= 1e-8);}
point top[MAXN],bot[MAXN];
int topc = 0,botc = 0;
double slope(point a,point b){return (a.y - b.y) / (a.x - b.x);}
double area(double a,double b,double c)
{
double p = (a + b + c) / 2;
return sqrt(p * (p - a) * (p - b) * (p - c));
}
double dis(point a,point b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}
double calc(point p1,point p2,point p3,point p4)
{
return area(dis(p1,p3),dis(p1,p2),dis(p2,p3)) + area(dis(p1,p4),dis(p3,p4),dis(p1,p3));
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p + 1,p + 1 + n,cmp_x);
for(int i = 1;i <= n;++i)
{
if(topc == 0){top[++topc] = p[i];continue;}
if(equal(p[i].x,top[topc].x)){if(p[i].y < top[topc].y)continue;else --topc;}
while(topc >= 2 && slope(top[topc],p[i]) >= slope(top[topc],top[topc - 1]))--topc;
top[++topc] = p[i];
}
for(int i = 1;i <= n;++i)
{
if(botc == 0){bot[++botc] = p[i];continue;}
if(equal(p[i].x,bot[botc].x)){if(p[i].y > bot[botc].y)continue;else --botc;}
while(botc >= 2 && slope(bot[botc],p[i]) <= slope(bot[botc],bot[botc - 1]))--botc;
bot[++botc] = p[i];
}
if(!equal(bot[botc].y,top[topc].y))top[++topc] = bot[botc];
for(int i = botc - 1;i >= 2;--i)top[++topc] = bot[i];
if(bot[1].y != top[1].y)top[++topc] = bot[1];
for(int i = 1;i <= topc;++i)top[i + topc] = top[i];
for(int i = 1;i <= 2 * topc;++i)p[i] = top[i];
double ans = 0;
for(int i = 1;i <= topc;++i)
{
int cur1 = i + 1,cur2 = i + 3;
for(int j = i + 2;j <= i + topc - 2;++j)
{
while(cur1 + 1 <= j && calc(p[cur1 + 1],p[i],p[cur2],p[j]) > calc(p[cur1],p[i],p[cur2],p[j]))++cur1;
while(cur2 + 1 < i + topc && calc(p[cur1],p[i],p[cur2 + 1],p[j]) > calc(p[cur1],p[i],p[cur2],p[j]))++cur2;
ans = max(ans,calc(p[cur1],p[i],p[cur2],p[j]));
}
}
printf("%.3lf\n",ans);
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡