给定一个多边形,要求在其内部找到一个点使得该点到边界的最短距离最长,求出该距离。
考虑二分距离
将所有的边向内推进
/**************************** * Au: Hany01 * Prob: [LA3890] [POJ3525] Most Distant Point from the Sea * Date: Feb 13th, 2018 * Email: hany01@foxmail.com ****************************/ #include#include #include #include #include #include #include #include #include #include
using namespace std; typedef long long LL; typedef pair PII; typedef vector VI; #define rep(i , j) for (int i = 0 , i##_end_ = j; i < i##_end_ ; ++ i) #define For(i , j , k) for (int i = (j) , i##_end_ = (k) ; i <= i##_end_ ; ++ i) #define Fordown(i , j , k) for (int i = (j) , i##_end_ = (k) ; i >= i##_end_ ; -- i) #define Set(a , b) memset(a , b , sizeof(a)) #define SZ(a) ((int)(a.size())) #define ALL(a) a.begin(), a.end() #define pb(a) push_back(a) #define mp(a, b) make_pair(a, b) #define INF (0x3f3f3f3f) #define INF1 (2139062143) #define Mod (1000000007) #define y1 wozenmezhemecaia #ifdef hany01 #define debug(...) fprintf(stderr , __VA_ARGS__) #else #define debug(...) #endif inline void File() { #ifdef hany01 freopen("la3890.in" , "r" , stdin); freopen("la3890.out" , "w" , stdout); #endif } template inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; } template inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; } inline int read() { register char c_; register int _ , __; for (_ = 0 , __ = 1 , c_ = getchar() ; !isdigit(c_) ; c_ = getchar()) if (c_ == '-') __ = -1; for ( ; isdigit(c_) ; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48); return _ * __; } const double eps = 1e-11; inline int dcmp(double x) { if (fabs(x) < eps) return 0; return x < 0 ? -1 : 1; } struct Point { double x, y; Point(double x = 0, double y = 0): x(x), y(y) {} }; typedef Point Vector; Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); } Vector operator * (Vector A, double p) { return Vector(A.x * p, A.y * p); } Vector operator / (Vector A, double p) { return Vector(A.x / p, A.y / p); } double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; } double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; } double Length(Vector A) { return sqrt(Dot(A, A)); } double Angle(Vector v) { return atan2(v.y, v.x); } Vector Normal(Vector v) { return Vector(-v.y, v.x) / Length(v); } struct Line { Point P; Vector v; double ang; Line(Point P = Point(0, 0), Vector v = Vector(0, 0)): P(P), v(v) { ang = Angle(v); } }; bool operator < (const Line& A, const Line& B) { return A.ang < B.ang; } inline bool OnLeft(Line L, Point p) { return dcmp(Cross(L.v, p - L.P)) > 0; } inline Point LineIntersection(Line A, Line B) { Vector u = A.P - B.P; double t = Cross(B.v, u) / Cross(A.v, B.v); return A.P + A.v * t; } const int maxn = 1000; inline int HalfplaneIntersection(Line* L, int n) { int head, tail; Point p[maxn]; Line q[maxn]; q[head = tail = 0] = L[1]; For(i, 2, n) { while (head < tail && !OnLeft(L[i], p[tail - 1])) -- tail; while (head < tail && !OnLeft(L[i], p[head])) ++ head; q[++ tail] = L[i]; if (!dcmp(Cross(q[tail].v, q[tail - 1].v))) { -- tail; if (OnLeft(q[tail], L[i].P)) q[tail] = L[i]; } if (head < tail) p[tail - 1] = LineIntersection(q[tail], q[tail - 1]); } while (head < tail && !OnLeft(q[head], p[tail - 1])) -- tail; if (head + 1 >= tail) return 0; return 1; } int n; Point p[maxn]; Line L[maxn], L_[maxn]; Vector dt[maxn]; int main() { File(); while (scanf("%d", &n) != EOF && n) { For(i, 1, n) scanf("%lf%lf", &p[i].x, &p[i].y); p[n + 1] = p[1]; For(i, 1, n) L[i] = Line(p[i], p[i + 1] - p[i]), dt[i] = Normal(p[i + 1] - p[i]); double l = 0, r = 20000.0, mid; while (r - l > eps) { mid = (l + r) * 0.5; For(i, 1, n) L_[i] = L[i], L_[i].P = L_[i].P + dt[i] * mid; sort(L_ + 1, L_ + 1 + n); if (HalfplaneIntersection(L_, n)) l = mid; else r = mid; } printf("%.6lf\n", l); } return 0; }