小粽圈地

小粽圈地

问题描述

小粽家里有一块地，地上有 nn 个木桩。小粽家的地可以看作是一个平面，并且小粽知道每个木桩的坐标 (xi,yi)(xi,yi)。

小粽很喜欢四边形，现在她想从这些木桩中选出 44 个来围成一个四边形（这个四边形为简单多边形，即每条边不能和自己相交，但不一定要为凸四边形），并使得这个四边形的面积最大。请你帮小粽算出这个最大值是多少。

输入格式

第一行一个正整数 nn 表示木桩的大小。

接下来 nn 行，第 ii 行位两个实数 xi,yixi,yi，描述了第 ii 个木桩的坐标。

输格式

输出一行一个实数，表示围出的最大的四边形的面积。保留三位小数。

输入样例 1

5

00

10

11

01

输样例 1

样例 2

点此下载。

数据范围及约定

20%20% 的数据满足 n ≤100n ≤100；

60%60% 的数据满足 n ≤400n ≤400；

80%80% 的数据满足 n ≤1500n ≤1500；

100%100% 的数据满足 n ≤5000n ≤5000，所有坐标都在 int 范围内。

提示

[显然，答案是在凸包上的]

[可以考虑枚举一条对角线，再设法确定另外两点的位置，例如注意到点的位置具有单峰性。]

[更可考虑求对角线与凸包的切点，利用单调性均摊复杂度]

代码

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<cmath>

#pragma warning(disable:4996) #define SF scanf

#define PF printf #define MAXN 10000 using namespace std; struct node {

double x, y;

node() {}

node(double xx, double yy) :x(xx), y(yy) {}

node operator + (const node &a) const {

return node(x + a.x, y + a.y);

}

node operator - (const node &a) const {

return node(x - a.x, y - a.y);

}

node operator * (const double &t) const {

return node(x*t, y*t);

}

double operator *(const node &a) const {

return x * a.x + y * a.y;

}

double operator ^(const node &a) const {

return x * a.y - y * a.x;

}

bool operator < (const node &a) const {

return x < a.x || (x == a.x&&y < a.y);

}

}p[MAXN], l1[MAXN];

stack<node> s1, s; double ans;

int n, cnt1;

void solve(node a1[], int &cnt) {

s.push(p[1]);

s1.push(p[1]);

s1.push(p[2]);

for (int i = 3; i <= n; i++) {

while (!s.empty() && ((p[i] - s.top()) ^ (s1.top() - s.top())) <= 0) {

s.pop();

s1.pop();

}

s.push(s1.top());

s1.push(p[i]);

}

while (!s1.empty()) {

a1[++cnt] = s1.top();

s1.pop();

}

while (!s.empty())

s.pop();

}

double sum(node a, node b, node c) {

return fabs((b - a) ^ (c - a));

}

bool cmp(node a, node b) {

return b < a;

}

int main() {

//freopen("data.in","r",stdin);

//freopen("data.out","w",stdout);

SF("%d", &n);

for (int i = 1; i <= n; i++)

SF("%lf%lf", &p[i].x, &p[i].y);

sort(p + 1, p + 1 + n);

solve(l1, cnt1);

sort(p + 1, p + 1 + n, cmp);

cnt1--;

solve(l1, cnt1);

cnt1--;

/*for(int i=1;i<=cnt1;i++)

PF("{%.2f %.2f}\n",l1[i].x,l1[i].y);*/

/*node t1=node(0,0);

node t2=node(1,1);

node t3=node(2,0);

PF("{%.3f}\n",sum(t1,t2,t3));*/

for (int i = 1; i <= cnt1; i++) {

int st1 = i % cnt1 + 1;

int j = (i + 1) % cnt1 + 1;

int st2 = (j + 1) % cnt1 + 1;

for (; j%cnt1 + 1 != i; j = j % cnt1 + 1) {

while (st1%cnt1 + 1 != j && sum(l1[i], l1[st1], l1[j]) < sum(l1[i], l1[st1%cnt1 + 1], l1[j]))

st1 = st1 % cnt1 + 1;

while (st2%cnt1 + 1 != i && sum(l1[i], l1[st2], l1[j]) < sum(l1[i], l1[st2%cnt1 + 1], l1[j]))

st2 = st2 % cnt1 + 1;

//PF("[%d(%.0f,%.0f) %d(%.0f,%.0f)-%d(%.0f,%.0f) %d(%.0f,%.0f) %.2f %.2f]\n",i,l1[i

].x,l1[i].y,st1,l1[st1].x,l1[st1].y,st2,l1[st2].x,l1[st2].y,j,l1[j].x,l1[j].y,sum(l1[i]

,l1[st1],l1[j])/2.0,sum(l1[i],l1[st2],l1[j])/2.0);

ans = max(ans, (sum(l1[i], l1[st1], l1[j]) + sum(l1[i], l1[st2], l1[j])) / 2.0);

}

}

PF("%.3lf", ans);

return 0;

}