首页 > 代码库 > poj 1113 Wall 凸包
poj 1113 Wall 凸包
1 /** 2 大意:给定点,求将这些点包起来的,最小周长,,形成的凸包与点之间的需要有一定的距离l; 3 思路: 1、求出凸包 4 2、求凸包中的长度+ 弧形的长度----〉即一个圆的周长: 因为形成的多边形的内角是360 所以因为距离l所形成的弧的角度相加即为360.。也就是一个圆的周长。。 5 值得学习:对于四舍五入。(int)(ans+ 0.5) 7 8 **/ 9 /#include <iostream> 10 #include <algorithm> 11 #include <cmath> 12 using namespace std; 13 const int maxn = 1050; 14 const double pi = acos(-1.0); 15 const double eps = 1e-8; 16 int dcmp(double x){ 17 if(fabs(x)<eps) return 0; 18 else 19 return x<0?-1:1; 20 } 21 int n; 22 struct point{ 23 double x,y; 24 point (double x=0,double y=0):x(x),y(y){} 25 }; 26 point p[maxn]; 27 point ch[maxn]; 28 typedef point Vector; 29 Vector operator - (point a , point b){ 30 return Vector (a.x-b.x,a.y-b.y); 31 } 32 33 double cross(Vector a,Vector b){ 34 return a.x*b.y-a.y*b.x; 35 } 36 double length(Vector a){ 37 return sqrt(a.x*a.x+a.y*a.y); 38 } 39 bool cmp(point a ,point b){ 40 if(a.x==b.x) 41 return a.y<b.y; 42 return a.x<b.x; 43 } 44 int convexHull(point *p,int n,point *ch){ // 凸包求法。 45 //cout<<"--------------->"<<endl; 46 sort(p,p+n,cmp); 47 // for(int i=0;i<n;i++) 48 // cout<<p[i].x<<" "<<p[i].y<<endl; 49 int m =0; 50 for(int i=0;i<n;i++){ 51 while(m>1&&dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0) 52 m--; 53 ch[m++] = p[i]; 54 } 55 int k= m; 56 for(int i=n-2;i>=0;i--){ 57 while(m>k&&dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]))<=0) 58 m--; 59 ch[m++] = p[i]; 60 } 61 //cout<<m<<endl; 62 if(n>1) m--; 63 return m; 64 } 65 66 int main() 67 { 68 int n,l; 69 cin>>n>>l; 70 for(int i=0;i<n;i++){ 71 cin>>p[i].x>>p[i].y; 72 } 73 int res = convexHull(p,n,ch); 74 //for(int i=0;i<res;i++) 75 // cout<<ch[i].x<<" "<<ch[i].y<<endl; 76 double ans =0; 77 for(int i=0;i<res-1;i++){ 78 ans += length(ch[i+1]-ch[i]); 79 } 80 ans += length(ch[res-1]-ch[0]); 81 //cout<<ans<<endl; 82 ans += pi*l*2; 83 cout<<(int )(ans+0.5)<<endl; 84 return 0; 85 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。