Most Distant Point from the Sea
二分离海距离, 按距离平移有向线段(“收缩”多边形),然后半平面求交验证
int main() { int n; while(~scanf("%d", &n),n) { vector<Point> p, v, normal; for(int i=0; i<n; ++i) { int x, y; scanf("%d%d", &x, &y); p.push_back(Point(x,y)); } for(int i=0; i<n; ++i){ v.push_back(p[(i+1)%n] - p[i]); normal.push_back(Normal(v[i])); } double l = 0, r = 20000, mid; while(r-l > eps){ vector<Line> L; mid = l + (r-l)/2; for(int i=0; i<n; ++i) L.push_back(Line(p[i]+normal[i]*mid, v[i])); if(HalfplaneIntersection(L).empty()) r = mid; else l = mid; } printf("%.6f\n", l); } return 0; }