首页 > 代码库 > POJ 3525 Most Distant Point from the Sea 二分+半平面交
POJ 3525 Most Distant Point from the Sea 二分+半平面交
题目大意:给出一个岛的海岸线的轮廓,求这个岛上的所有点到海岸的最长距离是多少。
思路:求多边形内切圆的问题要用二分+半平面交解决。二分半径的长度,然后将所有的边向左侧移动这个二分的长度,然后利用半平面交来判断是否能够满足条件。如果满足条件就提高下界,否则减小上界。
我的移动的方法是这样的,首先每条边都要用点向量式来表示,就是边上任意一点和这条边的方向向量。这样做以后的操作会方便很多。然后将每个直线的向左的法向量求出来(比如l的向量是v(x,y),那么它向左侧的法向量是(-y,x)),然后将法向量化成单位向量,然后这个直线方向向量不变,直线上的点向法向量方向移动二分的长度。详见代码。
CODE:
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 110 #define EPS 1e-10 #define DCMP(a) (fabs(a) < EPS) using namespace std; struct Point{ double x,y; Point(double _ = .0,double __ = .0):x(_),y(__) {} Point operator +(const Point &a)const { return Point(x + a.x,y + a.y); } Point operator -(const Point &a)const { return Point(x - a.x,y - a.y); } Point operator *(double a)const { return Point(x * a,y * a); } void Read() { scanf("%lf%lf",&x,&y); } }point[MAX],p[MAX]; struct Line{ Point p,v; double alpha; Line(Point _,Point __):p(_),v(__) { alpha = atan2(v.y,v.x); } Line() {} bool operator <(const Line &a)const { return alpha < a.alpha; } }line[MAX],q[MAX]; int points,lines; inline double Cross(const Point &a,const Point &b) { return a.x * b.y - a.y * b.x; } inline bool OnLeft(const Line &l,const Point &p) { return Cross(l.v,p - l.p) >= 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 < tail && !OnLeft(line[i],p[tail - 1])) --tail; while(front < tail && !OnLeft(line[i],p[front])) ++front; if(DCMP(Cross(line[i].v,q[tail].v))) q[tail] = OnLeft(line[i],q[tail].p) ? q[tail]:line[i]; else q[++tail] = line[i]; if(front < tail) p[tail - 1] = GetIntersection(q[tail],q[tail - 1]); } while(front < tail && !OnLeft(line[front],p[tail - 1])) --tail; if(tail - front <= 1) return false; return tail > 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 < points; ++i) MakeLine(point[i],point[i + 1],ans); MakeLine(point[points],point[1],ans); sort(line + 1,line + lines + 1); return HalfPlaneIntersection(); } int main() { while(scanf("%d",&points),points) { for(int i = 1;i <= points; ++i) point[i].Read(); double l = .0,r = 10000.0,ans = .0; while(r - l > 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 二分+半平面交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。