首页 > 代码库 > poj 1113 Wall

poj 1113 Wall

2024-07-02 15:12:55   224人阅读

题目链接：http://poj.org/problem?id=1113

题目大意：给出点集和一个长度L，要求用最短长度的围墙把所有点集围住，并且围墙每一处距离所有点的距离最少为L，求围墙的长度。

解法：凸包+以L为半径的圆的周长。以题目中的图为例，两点之间的围墙长度之和正好就是凸包的长度，再加上每个点的拐角处（注意此处为弧，才能保证城墙距离点的距离最短）的长度。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define inf 0x7fffffff
 8 #define exp 1e-10
 9 #define PI 3.141592654
10 using namespace std;
11 int n,L;
12 struct Point
13 {
14     double x,y;
15     Point (double x=0,double y=0):x(x),y(y){}
16     friend bool operator < (Point a,Point b)
17     {
18         if (a.x!=b.x) return a.x<b.x;
19         return a.y<b.y;
20     }
21 }an[1000+10],bn[1000+10];
22 typedef Point Vector;
23 Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x , A.y+B.y); }
24 Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x , A.y-B.y); }
25 Vector operator * (Vector A,double p) {return Vector(A.x*p , A.y*p); }
26 int dcmp(double x)
27 {
28     if (fabs(x)<exp) return 0;
29     else return x<0 ? -1 : 1;
30 }
31 double cross(Vector A,Vector B)
32 {
33     return A.x*B.y-B.x*A.y;
34 }
35 int ConvexHull(Point *p,int n,Point *ch)
36 {
37     sort(p,p+n);
38     int m=0;
39     for (int i=0 ;i<n ;i++)
40     {
41         while (m>1 && dcmp(cross(ch[m-1]-ch[m-2],p[i]-ch[m-1]))<=0) m--;
42         ch[m++]=p[i];
43     }
44     int k=m;
45     for (int i=n-2 ;i>=0 ;i--)
46     {
47         while (k>m && dcmp(cross(ch[k-1]-ch[k-2],p[i]-ch[k-1]))<=0) k--;
48         ch[k++]=p[i];
49     }
50     ch[k++]=ch[0];
51     if (n>1) k--;
52     return k;
53 }
54 int main()
55 {
56     while (cin>>n>>L)
57     {
58         for (int i=0 ;i<n ;i++)
59         scanf("%lf%lf",&an[i].x,&an[i].y);
60 
61         int k=ConvexHull(an,n,bn);
62         double sum=0;
63         sum += 2*PI*L;
64         for (int i=0 ;i<k ;i++)
65         {
66             sum += sqrt((bn[i].x-bn[i+1].x)*(bn[i].x-bn[i+1].x)+(bn[i].y-bn[i+1].y)*(bn[i].y-bn[i+1].y));
67         }
68         printf("%.0f\n",sum);
69     }
70     return 0;
71 }

 


联系
我们