求出凸包,显然四个点在凸包上。考虑枚举某点,再移动另一点作为对角线,容易发现剩下两点的最优位置是单调的。过程类似旋转卡壳。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 2010
#define vector point
#define nxt(i) (i%tail+1)
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n;
double ans;
const double eps=1E-8;
struct point
{
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};
}
double operator *(const vector&a) const
{
return x*a.y-y*a.x;
}
bool operator <(const point&a) const
{
return x<a.x||x==a.x&&y<a.y;
}
}a[N],b[N];
double area(point x,point z,point y)
{
return (y-x)*(z-x);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj1069.in","r",stdin);
freopen("bzoj1069.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1);
int tail=0;
for (int i=1;i<=n;i++)
{
while (tail>1&&(b[tail]-b[tail-1])*(a[i]-b[tail-1])<eps) tail--;
b[++tail]=a[i];
}
for (int i=n-1;i>=1;i--)
{
while (tail>1&&(b[tail]-b[tail-1])*(a[i]-b[tail-1])<eps) tail--;
b[++tail]=a[i];
}
for (int i=1;i<=tail;i++)
{
int p=nxt(i),q=nxt(i+2);
for (int j=i+2;j<=tail;j++)
{
while (nxt(p)!=i&&area(b[i],b[j],b[p])<area(b[i],b[j],b[nxt(p)])) p=nxt(p);
while (nxt(q)!=j&&area(b[i],b[q],b[j])<area(b[i],b[nxt(q)],b[j])) q=nxt(q);
ans=max(ans,area(b[i],b[j],b[p])+area(b[i],b[q],b[j]));//cout<<area(b[i],b[j],b[p])+area(b[i],b[q],b[j])<<endl;
}
}
printf("%.3f",ans/2);
return 0;
}

  

最新文章

  1. ROC &amp; AUC笔记
  2. javascript关于继承
  3. RMAN还原32位数据库到64位实例的错误处理
  4. React常用的API说明
  5. Azure Automation (1) 入门
  6. android xUtils get post
  7. C/C++ 关于大小端模式
  8. vs2012 Silverlight项目签名报错异常的处理方式
  9. 获取https证书
  10. IOS UI 第五篇:基本UI
  11. 2015级软工实践k班第一次作业-准备
  12. JAVA判断文件的内容类型
  13. Redis常见七种使用场景(PHP实战)
  14. 给我一台全新的服务器,使用nginx+gunicorn+supervisor部署django
  15. [Ext.Net]动态生成控件(二)--js动态添加文本框
  16. P1140 相似基因 (dp)
  17. C# 模拟 HTTP POST请求
  18. Where do I belong (freeCodeCamp)
  19. 图 总结 AI
  20. MySQL 命令操作数据表

热门文章

  1. 云主机被拿去挖矿,cpu暴涨,tcp连接突增
  2. CAN协议教程
  3. Django 学习 (第四部)
  4. 深入理解 JVM(上)
  5. React-UI组件和容器组件
  6. 微信小程序日常开发中常遇到的错误代码
  7. python3通过gevent.pool限制协程并发数量
  8. bootstrap面试题
  9. SCRUM 12.23
  10. javac编译提示错误需要为 class、interface 或 enum