首页 > 代码库 > hdu3847Trash Removal(凸包)

hdu3847Trash Removal(凸包)

链接

这题居然是WF的题, 应属于签到题。。

求一个多边形是否能被一个宽为d的矩形框住。

可以求一下凸包,然后枚举每条凸包的边,找出距离最远的点。

  1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 100000 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 const int MAXN=1550; 18 struct point 19 { 20     double x,y; 21     point(double x=0,double y=0):x(x),y(y){} 22 }p[N],ch[N]; 23 typedef point pointt; 24 point operator -(point a,point b) 25 { 26     return point(a.x-b.x,a.y-b.y); 27 } 28 int dcmp(double x) 29 { 30     if(fabs(x)<eps) return 0; 31     return x<0?-1:1; 32 } 33 double dis(point a,point b) 34 { 35     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 36 } 37 double cross(point a,point b) 38 { 39     return a.x*b.y-a.y*b.x; 40 } 41 double mul(point p0,point p1,point p2) 42 { 43     return cross(p1-p0,p2-p0); 44 } 45 double dis(point a) 46 { 47     return sqrt(a.x*a.x+a.y*a.y); 48 } 49 bool cmp(point a,point b) 50 { 51     if(dcmp(mul(p[0],a,b))==0) 52         return dis(a-p[0])<dis(b-p[0]); 53     else 54         return dcmp(mul(p[0],a,b))>0; 55 } 56 int Graham(int n) 57 { 58     int i,k = 0,top; 59     point tmp; 60     for(i = 0 ; i < n; i++) 61     { 62         if(p[i].y<p[k].y||(p[i].y==p[k].y&&p[i].x<p[k].x)) 63             k = i; 64     } 65     if(k!=0) 66     { 67         tmp = p[0]; 68         p[0] = p[k]; 69         p[k] = tmp; 70     } 71     sort(p+1,p+n,cmp); 72     ch[0] = p[0]; 73     ch[1] = p[1]; 74     top = 1; 75     for(i = 2; i < n ; i++) 76     { 77         while(top>0&&dcmp(mul(ch[top-1],ch[top],p[i]))<0) 78             top--; 79         top++; 80         ch[top] = p[i]; 81     } 82     return top; 83 } 84 double distancetoline(point p,point a,point b) 85 { 86     point v1 = b-a,v2 = p-a; 87     return fabs(cross(v1,v2))/dis(v1); 88 } 89 int main() 90 { 91     int i,j; 92     int n,kk=0; 93     while(scanf("%d",&n)&&n) 94     { 95         for(i = 0 ; i < n; i++) 96         scanf("%lf%lf",&p[i].x,&p[i].y); 97         int m = Graham(n); 98         ch[m+1] = ch[0]; 99         double ans = INF;100         for(i = 0 ; i <= m; i++)101         {102             double ts = 0;103             for(j = 0 ; j <= m ; j++)104             ts = max(ts,distancetoline(ch[j],ch[i],ch[i+1]));105             ans = min(ans,ts);106         }107         ans = ceil(ans*100)/100;108         printf("Case %d: %.2lf\n",++kk,ans);109     }110     return 0;111 }
View Code

 

hdu3847Trash Removal(凸包)