旋转卡壳就是对凸包用两条平行线夹着，然后绕着凸包的定点和边旋转，在旋转的过程中我们可以得到凸包的宽，直径等特征值，当然还可以计算其他东西。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#include <bits/stdc++.h> using namespace std; const int maxn=100+10; const double eps=1e-8; int dcmp(double x) { if (fabs(x)<eps) return 0; if (x>0) return 1; return -1; } struct point{ double x,y; point(){} point(double x,double y):x(x),y(y){} point operator + (const point & o) const{ return point(x+o.x,y+o.y); } point operator - (const point & o) const{ return point(x-o.x,y-o.y); } double operator ^ (const point & o) const { return x*o.y-y*o.x; } bool operator < (const point & o) const{ if (y==o.y) return x<o.x; return y>o.y; } void read() { scanf("%lf%lf",&x,&y); } double dis(const point & o) { return sqrt((x-o.x)*(x-o.x)+(y-o.y)*(y-o.y)); } } p[maxn]; double dis(point a,point b,point c) { double res= ((a-b)^(a-c))/b.dis(c); cerr<<res<<endl; return res; } bool cmp_x(const point &p,const point &q) { if (p.x!=q.x) return p.x<q.x; return p.y<q.y; } vector<point> convex_hull(point * ps,int n) { sort(ps,ps+n,cmp_x); int k=0; vector<point> qs(n*2); for (int i=0;i<n;i++) { while(k>1&&dcmp((qs[k-1]-qs[k-2])^(ps[i]-qs[k-1]))<=0) k--; qs[k++]=ps[i]; } int t=k; for (int i=n-2;i>=0;i--) { while(k>t&&dcmp((qs[k-1]-qs[k-2])^(ps[i]-qs[k-1]))<=0) k--; qs[k++]=ps[i]; } qs.resize(k-1); return qs; } int main() { int n; while(scanf("%d",&n)!=EOF) { for (int i=0;i<n;i++) { p[i].read(); } vector<point> pt=convex_hull(p,n); int l,r; int maxy,miny; maxy=-100005; miny=100005; for (int i=0;i<pt.size();i++) { if (pt[i].y>maxy) { maxy=pt[i].y; r=i; } if (pt[i].y<miny) { miny=pt[i].y; l=i; } } n=pt.size(); double ans=4*100000.0; int sl=l,sr=r; while(l!=sr||r!=sl) { int nl=(sl+1)%n; int nr=(sr+1)%n; if (dcmp((pt[nl]-pt[sl])^(pt[nr]-pt[sr]))<0) { ans=min(ans,dis(pt[sr],pt[sl],pt[nl])); sl=nl; } else { ans=min(ans,dis(pt[sl],pt[sr],pt[nr])); sr=nr; } } printf("%.10lf\n",ans); } return 0; } |
