1069: [SCOI2007]最大土地面积

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2560  Solved: 983

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<=2000, |x|,|y|<=100000

先求个凸包,然后枚举对角线,两边找面积最大的三角形

 /*by SilverN*/
 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<cstring>
 #include<algorithm>
 #define ll long long
 using namespace std;
 ;
 struct P{
     double x,y;
 }p[mxn],s[mxn];
 ;
 int n;
 ;
 //
 inline P operator - (P a,P b){
     P t; t.x=a.x-b.x; t.y=a.y-b.y; return t;
 }
 inline double operator * (P a,P b){
     return (a.x*b.y)-(b.x*a.y);
 }
 inline double dis(P a,P b){
     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
 }
 inline bool operator < (P a,P b){
     ])*(b-p[]);
     )])<dis(b,p[]);
     ;
 }
 //
 void graham(){
     ;
     int i,j;
     ;i<=n;i++){
         if(p[i].y<p[t].y || (p[i].y==p[t].y && p[i].x<p[t].x))t=i;
     }
     swap(p[],p[t]);
     sort(p+,p+n+);
     s[++top]=p[];s[++top]=p[];
     ;i<=n;i++){
          && (p[i]-s[top-])*(s[top]-s[top-])<=)
             top--;
         s[++top]=p[i];
     }
     s[top+]=p[];
     return;
 }
 double solve()
 {
     s[top+]=p[];
     ;
     int a,b;
     ;x<=top;x++)
     {
         a=x%top+;b=(x+)%top+;
         ;y<=top;y++)
         {
             !=y&&(s[y]-s[x])*(s[a+]-s[x])>(s[y]-s[x])*(s[a]-s[x]))
                 a=a%top+;
             !=x&&(s[b+]-s[x])*(s[y]-s[x])>(s[b]-s[x])*(s[y]-s[x]))
                 b=b%top+;
             ans=max((s[y]-s[x])*(s[a]-s[x])+(s[b]-s[x])*(s[y]-s[x]),ans);//(s[b]-s[x])*(s[y]-s[x])前后颠倒成(s[y]-s[x])*(s[b]-s[x])就会WA,不能理解
         }
     }
     return ans;
 }
 int main(){
     scanf("%d",&n);
     int i,j;
     ;i<=n;i++){
         scanf("%lf%lf",&p[i].x,&p[i].y);
     }
     graham();
     printf();
     ;
 }

最新文章

  1. windows中LNK文件打开方式恢复(每日一修(1))
  2. Collection集合的功能及总结
  3. iOS OC语言: Block底层实现原理
  4. 移动端网页fixed布局问题解决方案
  5. css3制作惊艳hover切换效果
  6. QC学习三:Excel数据导入导出QC操作流程
  7. NodeJS学习笔记之MongoDB模块
  8. 使用astyle格式化代码
  9. crm维护踩坑记(一)
  10. MySQL Crash Errcode: 28 - No space left on device
  11. vscode在vue-cli中按照ESlint自动格式化代码
  12. 设计模式&lt;2&gt;------工厂模式和抽象工厂模式------创建型
  13. [论文阅读]Object detection at 200 Frames Per Second
  14. SQL Server - NOLOCK
  15. Python pyc知识了解
  16. 内存泄露java.lang.OutOfMemoryError: PermGen space解决方法
  17. SWAP 简介
  18. React Native 学习资料
  19. TCP/UDP端口列表(WIKIpedia)
  20. 夏天过去了, 姥爷推荐几套来自smashingmagzine的超棒秋天主题壁纸

热门文章

  1. 使用List的addAll()方法请判空指针
  2. java 14-2 正则表达式的案例
  3. PNG文件
  4. Thread锁 Monitor类、Lock关键字和Mutex类
  5. 024医疗项目-模块二:药品目录的导入导出-HSSF导入类的学习
  6. 学习node.js 第4篇 建立一个最小的web聊天系统
  7. Asp.net通过Jquery操作WebService进行Ajax读写
  8. 对SharePreference的封装
  9. Activiti系列:如何让Activiti-Explorer使用sql server数据库
  10. Windows下虚拟机安装Mac OS X ----- VM12安装Mac OS X 10.11