首页 > 代码库 > 计算几何-RC-poj2187

计算几何-RC-poj2187

2024-09-12 00:13:31   217人阅读

今天学习一下旋(xuan1)转(zhuan3)卡(qia3)壳(qiao4)

1.凸包

2.对踵点

定理：最远点对必然属于对踵点对集合

对踵点定义：

        如果过凸包上的两个点可以画一对平行直线，使凸包上的所有点都

夹在两条平行线之间或落在平行线上，那么这两个点叫做一对对踵点。

 

具体有两种情况：

技术分享

技术分享

1.两个平行线正好卡着两个点

2.两个平行线分别卡着一条边和一个点

Rotating calipers Algorithm 是基于情况2的

 

        考虑到，固定一条边，凸包上的点到线的距离构成一个单峰函数，

所以，有“单调性”(姑且叫做单调性)

 

技术分享

 

 

直观的感受一下

 

 

技术分享

 

 

 

 

post the Rujia Liu ‘s words :

/*
    当Area(p[u], p[u+1], p[v+1]) <= Area(p[u], p[u+1], p[v])时停止旋转
    即Cross(p[u+1]-p[u], p[v+1]-p[u]) - Cross(p[u+1]-p[u], p[v]-p[u]) <= 0
    根据Cross(A,B) - Cross(A,C) = Cross(A,B-C)
    化简得Cross(p[u+1]-p[u], p[v+1]-p[v]) <= 0
*/

旋转code

 

技术分享 
 1 db RC(D*R,int n){//Rotating calipers
 2   R[0]=R[n];// avoid to mod
 3   db ans=0.0;
 4   for(int u=0,v=1;u<n;u++){
 5     while(Cross(R[u+1]-R[u],R[v+1]-R[v])>0)v=(v+1)%n;
 6     ans=max(ans,Dis2(R[u],R[v]));
 7     ans=max(ans,Dis2(R[u+1],R[v+1]));
 8   }
 9   return ans;
10 }
RC

 

 

一个小技巧，手写unique（其实是不会用STL，PS:不去重可以过）

 

技术分享 
1 bl operator==(D A,D B){return (fabs(A.x-B.x)<eps && fabs(A.y-B.y)<eps);}
2 
3 void Unique(D*R,int&n){
4   bl*In=new bl[n];
5   for(int i=1;i<=n;i++)if(R[i+1]==R[i])In[i+1]=1;else In[i]=0;
6   int cnt=0;
7   for(int i=1;i<=n;i++)if(!In[i])R[++cnt]=R[i];
8   n=cnt;
9 }
Unique

 

 

 

ACcode

 

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <cmath>
 8 #include <queue>
 9 #include <map>
10 #include <set>
11 using namespace std;
12 #define sqr(x) ((x)*(x))
13 #define RG register
14 #define op operator
15 #define IL inline
16 typedef double db;
17 typedef bool bl;
18 const db pi=acos(-1.0),eps=1e-10;
19 struct D{
20   db x,y;
21   D(db x=0.0,db y=0.0):x(x),y(y){}
22 };
23 typedef D V;
24 bl operator<(D A,D B){return A.x<B.x||(A.x==B.x&&A.y<B.y);}
25 bl operator==(D A,D B){return (fabs(A.x-B.x)<eps && fabs(A.y-B.y)<eps);}
26 V operator+(V A,V B){return V(A.x+B.x,A.y+B.y);}
27 V operator-(V A,V B){return V(A.x-B.x,A.y-B.y);}
28 V operator*(V A,db N){return V(A.x*N,A.y*N);}
29 V operator/(V A,db N){return V(A.x/N,A.y/N);}
30 
31 db Ang(db x){return(x*180.0/pi);}
32 db Rad(db x){return(x*pi/180.0);}
33 V Rotate(V A,db a){return V(A.x*cos(a)-A.y*sin(a),A.x*sin(a)+A.y*cos(a));}
34 db Dis2(D A,D B){return sqr(A.x-B.x)+sqr(A.y-B.y);}
35 db Dis(D A,D B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}
36 db Cross(V A,V B){return A.x*B.y-A.y*B.x;}
37 db Dot(V A,V B){return A.x*B.x+A.y*B.y;}
38 
39 void Unique(D*R,int&n){
40   bl*In=new bl[n];
41   for(int i=1;i<=n;i++)if(R[i+1]==R[i])In[i+1]=1;else In[i]=0;
42   int cnt=0;
43   for(int i=1;i<=n;i++)if(!In[i])R[++cnt]=R[i];
44   n=cnt;
45 }
46 
47 int Andrew(D*R,int&n,D*A){
48   int m=0;
49   sort(R+1,R+n+1);
50   Unique(R,n);
51   for(int i=1;i<=n;i++){
52     while(m>=2 && Cross(A[m]-A[m-1],R[i]-A[m-1])<=0)m--;
53     A[++m]=R[i];
54   }
55   int k=m;
56   for(int i=n-1;i>=1;i--){
57     while(m>k  && Cross(A[m]-A[m-1],R[i]-A[m-1])<=0)m--;
58     A[++m]=R[i];
59   }
60   return n>1?m-1:m;
61 }
62 
63 db RC(D*R,int n){    //Rotating calipers
64   R[0]=R[n];             // avoid to mod
65   db ans=0.0;
66   for(int u=0,v=1;u<n;u++){
67     while(Cross(R[u+1]-R[u],R[v+1]-R[v])>0)v=(v+1)%n;
68     ans=max(ans,Dis2(R[u],R[v]));
69     ans=max(ans,Dis2(R[u+1],R[v+1]));
70   }
71   return ans;
72 }
73 
74 const int MAXN=(int)4e5+10;
75 D R[MAXN],T[MAXN];
76 
77 int main(){
78   int n;scanf("%d",&n);
79   for(int i=1;i<=n;i++)scanf("%lf%lf",&R[i].x,&R[i].y);
80   int m=Andrew(R,n,T);
81   printf("%.0lf\n",RC(T,m));
82   return 0;
83 }

 

计算几何-RC-poj2187


联系
我们