博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
计算几何基础
阅读量:5116 次
发布时间:2019-06-13

本文共 4784 字,大约阅读时间需要 15 分钟。

凸包算法

http://poj.org/problem?id=3348

#include
#include
using namespace std;const int N=5e5+11;int n,m;struct point{ int x,y; point(){} point(int _x,int _y): x(_x),y(_y){} friend inline point operator -(const point A,const point B){ return point(A.x-B.x,A.y-B.y); } friend inline int operator *(const point A,const point B){ return A.x*B.y-A.y*B.x; } inline int norm(){ return x*x+y*y; }}p[N],q[N];inline bool operator <(const point A,const point B){ int det=(A-p[1])*(B-p[1]); if(det!=0)return det>0; return (A-p[1]).norm()<(B-p[1]).norm();}inline void Graham(){ int id=1; for(register int i=2;i<=n;++i) if(p[i].x
=2&&(p[i]-q[m-1])*(q[m]-q[m-1])>=0)--m; q[++m]=p[i]; }}inline int Area(){ int res=0; q[m+1]=q[1]; for(register int i=1;i<=m;++i) res+=q[i]*q[i+1]; return (res>>1);}int main(){ scanf("%d",&n); for(register int i=1;i<=n;++i)scanf("%d%d",&p[i].x,&p[i].y); Graham(); printf("%d\n",Area()/50); return 0;}

  

旋转卡壳

http://poj.org/problem?id=2187

#include
#include
using namespace std;const int N=5e5+11;int n,m;inline int max(int a,int b){ return a>b?a:b;}struct point{ int x,y; point(){} point(int _x,int _y): x(_x),y(_y){} friend inline point operator -(const point A,const point B){ return point(A.x-B.x,A.y-B.y); } friend inline int operator *(const point A,const point B){ return A.x*B.y-A.y*B.x; } inline int norm()const{ return x*x+y*y; }}p[N],q[N];inline bool operator <(const point A,const point B){ int det=(A-p[1])*(B-p[1]); if(det!=0)return det>0; return (A-p[1]).norm()<(B-p[1]).norm();}inline void Graham(){ int id=1; for(register int i=2;i<=n;++i) if(p[i].x
=2&&(p[i]-q[m-1])*(q[m]-q[m-1])>=0)--m; q[++m]=p[i]; }}inline int nxt(int x){ return x%m+1;}inline int area(const point A,const point B,const point C){ return (B-A)*(C-A);}inline int query(){ if(m==2)return (q[2]-q[1]).norm(); int res=0; for(register int i=1,j=3;i<=m;++i){ while(nxt(j)!=i&&area(q[i],q[i+1],q[j])<=area(q[i],q[i+1],q[nxt(j)]))j=nxt(j); res=max(res,(q[i+1]-q[j]).norm()); res=max(res,(q[i]-q[j]).norm()); } return res;}int main(){ scanf("%d",&n); for(register int i=1;i<=n;++i)scanf("%d%d",&p[i].x,&p[i].y); Graham(); printf("%d\n",query()); return 0;}

  

BZOJ1069

http://www.lydsy.com/JudgeOnline/problem.php?id=1069

先做凸包,再枚举凸包的对角线,对于剩下的两个凸多边形做旋转卡壳

#include
#include
using namespace std;typedef double db;int n,m;const int N=1e6+11;struct point{ db x,y; point(){} point(db _x,db _y): x(_x),y(_y){} friend inline point operator-(const point A,const point B){ return point(A.x-B.x,A.y-B.y); } friend inline db operator*(const point A,const point B){ return A.x*B.y-A.y*B.x; } inline db norm()const{ return x*x+y*y; }}p[N],q[N];inline bool operator<(const point A,const point B){ db det=(A-p[1])*(B-p[1]); if(det!=0)return det>0; return (A-p[1]).norm()<(B-p[1]).norm();}inline void Graham(){ for(register int i=2;i<=n;++i) if(p[i].x
1&&(p[i]-q[m-1])*(q[m]-q[m-1])>=0)--m; q[++m]=p[i]; }}inline int nxt(int x){ return x%m+1;}inline db abs(db x){ return x>=0?x:-x;}inline db max(db a,db b){ return a>=b?a:b;}inline db solve(){ db ans=0; q[m+1]=q[1]; for(register int i=1,k,l;i<=m;++i){ l=nxt(nxt(k=nxt(i))); for(register int j=nxt(k);j<=m;++j){ while(nxt(k)!=j&&abs((q[k]-q[i])*(q[j]-q[i]))<=abs((q[nxt(k)]-q[i])*(q[j]-q[i])))k=nxt(k); while(nxt(l)!=i&&abs((q[l]-q[i])*(q[j]-q[i]))<=abs((q[nxt(l)]-q[i])*(q[j]-q[i])))l=nxt(l); ans=max(ans,1.00*(abs((q[k]-q[i])*(q[j]-q[i]))+abs((q[l]-q[i])*(q[j]-q[i])))); } } return ans*1.00/2.00;}int main(){ scanf("%d",&n); for(register int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y); Graham(); printf("%.3lf",solve()); return 0;}

  

BZOJ1185

http://www.lydsy.com/JudgeOnline/problem.php?id=1185

先做凸包,再枚举凸包的一条边,用旋转卡壳做出该边的平行线,然后用点积求矩形宽的极值(具有单调性)

复杂度O(n^2)

#include
#include
#include
#define eps 1e-8#define inf 1000000000using namespace std;double ans=1e60;int n,top;struct P{ double x,y; P(){} P(double _x,double _y):x(_x),y(_y){} friend inline bool operator<(P a,P b){ return fabs(a.y-b.y)
0;}inline void graham(){ for(register int i=2;i<=n;++i) if(p[i]
1&&(q[top]-q[top-1])*(p[i]-q[top])
-eps)p=(p+1)%top; while((q[i+1]-q[i])/(q[r+1]-q[i])-(q[i+1]-q[i])/(q[r]-q[i])>-eps)r=(r+1)%top; if(i==0)l=r; while((q[i+1]-q[i])/(q[l+1]-q[i])-(q[i+1]-q[i])/(q[l]-q[i])

  

转载于:https://www.cnblogs.com/Stump/p/8410883.html

你可能感兴趣的文章
了解node.js
查看>>
想做移动开发,先看看别人怎么做
查看>>
Eclipse相关集锦
查看>>
虚拟化架构中小型机构通用虚拟化架构
查看>>
继承条款effecitve c++ 条款41-45
查看>>
HTML+CSS学习笔记(九)
查看>>
Java泛型的基本使用
查看>>
1076 Wifi密码 (15 分)
查看>>
rsync
查看>>
noip模拟赛 党
查看>>
bzoj2038 [2009国家集训队]小Z的袜子(hose)
查看>>
Java反射机制及其Class类浅析
查看>>
Postman-----如何导入和导出
查看>>
移动设备显示尺寸大全 CSS3媒体查询
查看>>
hihoCoder #1831 : 80 Days-RMQ (ACM/ICPC 2018亚洲区预选赛北京赛站网络赛)
查看>>
图片等比例缩放及图片上下剧中
查看>>
WebView加载网页详情
查看>>
【转载】Linux screen 命令详解
查看>>
dd命令 建立两颗一模一样的磁盘
查看>>
常用的jquery触屏手机页面特效代码下载
查看>>