题目链接~

1069: [SCOI2007]最大土地面积

思路很简单,极角排序求完凸包后,在凸包上枚举对角线,然后两边分别来两个点旋转卡壳一下,搞定!

不过计算几何的题目就是这样,程序中间的处理还是比较麻烦的,写的时候要很小心,特别是存点和枚举的时候要注意是个循环。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm> #define For(i,a,b) for(register int i=a;i<=b;++i)
#define Dwn(i,a,b) for(register int i=a;i>=b;--i)
#define Re register using namespace std; const int N=; struct P{
double x,y;
}st[N],O,p[N];
int n,top=-; P operator -(P a,P b){
P t; t.x=a.x-b.x; t.y=a.y-b.y; return t;
}
double operator *(P a,P b){
return a.x*b.y-b.x*a.y;
}
double Dis(P a,P b){
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
int Xx(P a){
if(a.x-O.x> &&a.y-O.y>=)return ;
if(a.x-O.x<=&&a.y-O.y> )return ;
if(a.x-O.x< &&a.y-O.y<=)return ;
if(a.x-O.x>=&&a.y-O.y< )return ;
}
bool cmp(const P a,const P b){
int aX=Xx(a);
int bX=Xx(b);
if(aX!=bX)return aX<bX;
double cx= (a-O)*(b-O);
if(cx==)return a.x<b.x;
else return cx>;
}
bool cmpY(const P a,const P b){
return a.y<b.y;
} void TuBao(){
st[++top]=p[];
st[++top]=p[];
For(i,,n+){
while( (p[i]-st[top-])*(st[top]-st[top-])>= ) top--;
st[++top]=p[i];
}
} double ans=;
void SpinStir(){
P p1,p2;
int i1,i2;
For(x,,top-){
i1=(x+)%top; p1=st[i1];
i2=(x+)%top; p2=st[i2];
For(y,x+,top-){
int Ni; P Np; Ni=(i1+)%top;
Np=st[Ni];
while(Ni!=x&&(Np-st[y])*(st[x]-st[y])>(p1-st[y])*(st[x]-st[y])){
i1=Ni; p1=Np; Ni=(i1+)%top; Np=st[Ni];
} Ni=(i2+)%top;
Np=st[Ni];
while(Ni!=y&&(Np-st[x])*(st[y]-st[x])>(p2-st[x])*(st[y]-st[x])){
i2=Ni; p2=Np; Ni=(i2+)%top; Np=st[Ni];
} double Sm=(p1-st[y])*(st[x]-st[y])/ + (p2-st[x])*(st[y]-st[x])/;
ans=max(ans,Sm);
}
}
} int main(){
//freopen("ex.in","r",stdin); scanf("%d",&n);
For(i,,n){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
sort(p+,p+n+,cmpY);
O=p[];
sort(p+,p+n+,cmp);
p[n+]=p[];
TuBao();
SpinStir();
printf("%.03lf",ans);
return ; }

最新文章

  1. Android 使用pull,sax解析xml
  2. Combinations
  3. Python控制window进行简单的消息弹窗
  4. 问题解决_WCF_WCF 接收我服务的 HTTP 响应时发生错误
  5. Unity使用反射探头实现地面的镜面反射
  6. Hadoop MapReduce编程 API入门系列之小文件合并(二十九)
  7. 本地Mac如何搭建IPv6环境
  8. MVC上传文件示例
  9. PHP面向对象三大特点学习(充分理解抽象、封装、继承、多态)
  10. C++ Generate Rand Number Array by &quot;srand()&quot; 生成随机数
  11. iOS工程预编译文件的创建
  12. Leap Motion 开发笔记
  13. Hash Table Performance in R: Part I(转)
  14. AI_神经网络监督学习
  15. 【Ansible】 基于SSH的远程管理工具
  16. C++ STL基本容器使用
  17. Spring Boot获取前端页面参数的几种方式总结
  18. GigE IP地址配置
  19. 如何对接oracle 建立pdb
  20. RabbitMQ系列教程之一:我们从最简单的事情开始!Hello World(转载)

热门文章

  1. 使用diff制作补丁【学习笔记】
  2. 理解SQL原理,写出高效的SQL语句
  3. Spark- Spark Yarn模式下跑yarn-client无法初始化SparkConext,Over usage of virtual memory
  4. 【boost】使用serialization库序列化子类
  5. swift的arc 是不是有问题?
  6. 树莓派与 Python —— GPIO
  7. BrowserSync(省时的浏览器同步测试工具)
  8. 「UVA557」 Burger(概率
  9. python爬虫知识点总结(五)正则表达式
  10. TCP头部格式详解,附Wireshark对TCP头部抓包分析