POJ3525MostDistantPointfromtheSea二分+半平面交

题目大意：给出一个岛的海岸线的轮廓，求这个岛上的所有点到海岸的最长距离是多少。

思路：求多边形内切圆的问题要用二分+半平面交解决。二分半径的长度，然后将所有的边向左侧移动这个二分的长度，然后利用半平面交来判断是否能够满足条件。如果满足条件就提高下界，否则减小上界。

我的移动的方法是这样的，首先每条边都要用点向量式来表示，就是边上任意一点和这条边的方向向量。这样做以后的操作会方便很多。然后将每个直线的向左的法向量求出来（比如l的向量是v(x,y)，那么它向左侧的法向量是(-y,x)），然后将法向量化成单位向量，然后这个直线方向向量不变，直线上的点向法向量方向移动二分的长度。详见代码。

CODE：

#include 
#include 
#include 
#include 
#include 
#define MAX 110
#define EPS 1e-10
#define DCMP(a) (fabs(a) = 0;
}

inline double Calc(const Point &a,const Point &b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + 
				(a.y - b.y) * (a.y - b.y));
}

inline Point GetIntersection(const Line &a,const Line &b)
{
	Point u = a.p - b.p;
	double temp = Cross(b.v,u) / Cross(a.v,b.v);
	return a.p + a.v * temp;
}

inline bool HalfPlaneIntersection()
{
	int frOnt= 1,tail = 1;
	q[tail] = line[1];
	for(int i = 2;i <= lines; ++i) {
		while(front  front;
}

inline void MakeLine(const Point &a,const Point &b,double adjustment)
{
	Point p = a,v = b - a;
	double length = Calc(a,b);
	Point _v(-v.y / length,v.x / length);
	p = p + _v * adjustment;
	line[++lines] = Line(p,v);
}

inline bool Judge(double ans)
{
	lines = 0;
	for(int i = 1;i  EPS) {
			double mid = (l + r) * 0.5;
			if(Judge(mid))	l = mid,ans = mid;
			else	r = mid;
		}
		printf("%.6lf\n",ans);
	}
	return 0;
}

POJ 3525 Most Distant Point from the Sea 二分+半平面交