[ UVA ] 1396 - Most Distant Point from the Sea

題目:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4142

解法:
這題要算距離圖多邊形邊最遠的點，想法是半平面交+二分搜尋，每次把多邊形的每條邊向內移動m單位，之後判斷半平面交面積是否為0，搜尋m的邊界

code:

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

#include<bits/stdc++.h> using namespace std; template<typename T> struct point{ T x,y; point(){} point(const T&dx,const T&dy):x(dx),y(dy){} inline const point operator+(const point &b)const{ return point(x+b.x,y+b.y); } inline const point operator-(const point &b)const{ return point(x-b.x,y-b.y); } inline const point operator*(const T &b)const{ return point(x*b,y*b); } inline const point operator/(const T &b)const{ return point(x/b,y/b); } inline const T dot(const point &b)const{ return x*b.x+y*b.y; } inline const T cross(const point &b)const{ return x*b.y-y*b.x; } inline point normal()const{/*求法向量*/ return point(-y,x); } inline const T abs2()const{/*向量長度的平方*/ return dot(*this); } }; template<typename T> struct line{ line(){} point<T> p1,p2; line(const point<T>&x,const point<T>&y):p1(x),p2(y){} inline bool parallel(const line &l)const{/*直線平行*/ return (p1-p2).cross(l.p1-l.p2)==0; } inline T cross(const point<T> &p)const{/*點和有向直線的關係，>0左邊、=0在線上<0右邊*/ return (p2-p1).cross(p-p1); } inline point<T> line_intersection(const line &l)const{/*直線交點*/ point<T> a=p2-p1,b=l.p2-l.p1,s=l.p1-p1; return p1+a*s.cross(b)/a.cross(b); } }; template<typename T> struct polygon{ polygon(){} std::vector<point<T> > p; inline const point<T>& operator[](int id)const{ return p[id]; } inline static char sign(const T&x){ return x>=0?1:-1; } inline static bool angle_cmp(const line<T>& A,const line<T>& B){ point<T>a=A.p2-A.p1,b=B.p2-B.p1; char ay=sign(a.y),by=sign(b.y),ax=sign(a.x),bx=sign(b.x); return ay>by||(ay==by&&(ax*ay>bx*by||(ax*ay==bx*by&&a.cross(b)>0))); } inline int halfplane_intersection(std::vector<line<T> > &s){ sort(s.begin(),s.end(),angle_cmp); int L,R,n=s.size(); std::vector<point<T> > px(n); std::vector<line<T> > q(n); q[L=R=0]=s[0]; for(int i=1;i<n;++i){ while(L<R&&s[i].cross(px[R-1])<=0)--R; while(L<R&&s[i].cross(px[L])<=0)++L; q[++R]=s[i]; if(q[R].parallel(q[R-1])){ --R; if(q[R].cross(s[i].p1)>0)q[R]=s[i]; } if(L<R)px[R-1]=q[R-1].line_intersection(q[R]); } while(L<R&&q[L].cross(px[R-1])<=0)--R; p.clear(); if(R-L<=1)return 0; px[R]=q[R].line_intersection(q[L]); for(int i=L;i<=R;++i)p.push_back(px[i]); return R-L+1; } }; int n; vector<line<double> > l; point<double> p[200],v[200],v2[200]; polygon<double> poly; int main(){ while(scanf("%d",&n)&&n){ for(int i=0;i<n;++i) scanf("%lf%lf",&p[i].x,&p[i].y); for(int i=0;i<n;++i){ v[i]=p[(i+1)%n]-p[i]; v2[i]=v[i].normal()/sqrt(v[i].abs2()); } l.resize(n); double L=0,R=10000;//二分搜 while(R-L>1e-8){ double mid=L+(R-L)/2; for(int i=0;i<n;++i) l[i]=line<double>(p[i]+v2[i]*mid,p[i]+v2[i]*mid+v[i]); int m=poly.halfplane_intersection(l); if(!m)R=mid; else L=mid; } printf("%.6lf\n",L); } return 0; }