Most Distant Point from the Sea POJ - 3525

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<math.h>
  6 #define eps 1e-8
  7 #define PI acos(-1.0)
  8 #define MAXN 110
  9 using namespace std;
 10 
 11 int n;
 12 
 13 int sgn(double x)
 14 { //符号函数
 15     if(fabs(x) < eps) return 0;
 16     if(x < 0) return -1;
 17     else return 1;
 18 }
 19 
 20 struct Point
 21 { //点 
 22     double x,y;
 23     Point(){}
 24     Point(double _x,double _y)
 25     {
 26         x = _x; y = _y;
 27     }
 28     Point operator -(const Point &b)const
 29     {
 30         return Point(x - b.x, y - b.y);
 31     }
 32     double operator ^(const Point &b)const
 33     { //叉积
 34         return x*b.y - y*b.x;
 35     }
 36     double operator *(const Point &b)const
 37     { //点积
 38         return x*b.x + y*b.y;
 39     }
 40 };
 41 
 42 struct Line
 43 { //向量 
 44     Point s,e; //两点
 45     double k; //斜率
 46     Line(){}
 47     Line(Point _s,Point _e)
 48     { //构造
 49         s = _s; e = _e;
 50         k = atan2(e.y - s.y,e.x - s.x);
 51     }
 52     Point operator &(const Line &b)const
 53     { //求两直线交点
 54         Point res = s;
 55         double t = ((s - b.s)^(b.s - b.e))/((s - e)^(b.s - b.e));
 56         res.x += (e.x - s.x)*t;
 57         res.y += (e.y - s.y)*t;
 58         return res;
 59     }
 60 };
 61 
 62 Line Q[MAXN];
 63 Point p[MAXN]; //记录最初给的点集
 64 Line line[MAXN]; //由最初的点集生成直线的集合
 65 Point pp[MAXN]; //记录半平面交的结果的点集
 66 
 67 //半平面交，直线的左边代表有效区域
 68 bool HPIcmp(Line a,Line b)
 69 { //直线排序函数
 70     if(fabs(a.k - b.k) > eps)return a.k < b.k; //斜率排序
 71     
 72     return ((a.s - b.s)^(b.e - b.s)) < 0;
 73 }
 74 
 75 void HPI(Line line[], int n, Point res[], int &resn)
 76 { //line是半平面交的直线的集合 n是直线的条数 res是结果
 77 //的点集 resn是点集里面点的个数
 78     int tot = n;
 79     sort(line,line+n,HPIcmp);
 80     tot = 1;
 81     for(int i = 1;i < n;i++)
 82         if(fabs(line[i].k - line[i-1].k) > eps) //去掉斜率重复的
 83             line[tot++] = line[i];
 84     int head = 0, tail = 1;
 85     Q[0] = line[0];
 86     Q[1] = line[1];
 87     resn = 0;
 88     for(int i = 2; i < tot; i++)
 89     {
 90         if(fabs((Q[tail].e-Q[tail].s)^(Q[tail-1].e-Q[tail-1].s)) < eps ||
 91            fabs((Q[head].e-Q[head].s)^(Q[head+1].e-Q[head+1].s)) < eps)
 92             return;
 93         while(head < tail && (((Q[tail]&Q[tail-1]) -
 94                                line[i].s)^(line[i].e-line[i].s)) > eps)
 95             tail--;
 96         while(head < tail && (((Q[head]&Q[head+1]) -
 97                                line[i].s)^(line[i].e-line[i].s)) > eps)
 98             head++;
 99         Q[++tail] = line[i];
100     }
101     while(head < tail && (((Q[tail]&Q[tail-1]) -
102                            Q[head].s)^(Q[head].e-Q[head].s)) > eps)
103         tail--;
104     while(head < tail && (((Q[head]&Q[head-1]) -
105                            Q[tail].s)^(Q[tail].e-Q[tail].e)) > eps)
106         head++;
107     if(tail <= head + 1) return;
108     for(int i = head; i < tail; i++)
109         res[resn++] = Q[i]&Q[i+1];
110     if(head < tail - 1)
111         res[resn++] = Q[head]&Q[tail];
112 }
113 
114 double dist(Point a,Point b)
115 { //两点间距离
116     return sqrt((a-b)*(a-b));
117 }
118 
119 void change(Point a,Point b,Point &c,Point &d,double p)
120 { //将线段ab往左移动距离p,修改得到线段cd
121     double len=dist(a,b);
122     /*三角形相似推出下面公式*/
123     double dx=(a.y-b.y)*p/len;
124     double dy=(b.x-a.x)*p/len;
125     c.x=a.x+dx; c.y=a.y+dy;
126     d.x=b.x+dx; d.y=b.y+dy;
127 }
128 
129 double BSearch()
130 { //二分搜索 
131     double l=0,r=100000;
132     double ans=0;
133     while(r-l>=eps)
134     {
135         double mid=(l+r)/2;
136         for(int i=0;i < n;i++)
137         {
138             Point t1,t2;
139             change(p[i],p[(i+1)%n],t1,t2,mid);
140             line[i]=Line(t1,t2);
141         }
142         int resn;
143         HPI(line,n,pp,resn);
144         //等于0说明移多了
145         if(resn==0) r=mid-eps;
146         else l=mid+eps;
147     }
148     return l;
149 }
150 
151 int main()
152 {
153     while(~scanf("%d",&n)&&n)
154     {
155         for(int i = 0;i < n;i++)
156             scanf("%lf%lf",&p[i].x,&p[i].y);
157         printf("%.6f\n",BSearch());
158     }
159     return 0;
160 }