CodeForces 772B Volatile Kite

计算几何，直觉。

凭直觉猜的做法，把每条线段的中点连起来，每个点到对应内部线段的距离，取个最小值。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <stack>

#include <vector>

#include <algorithm>

using namespace std;

#define eps 1e-8

#define zero(x)(((x)>0?(x):-(x))<eps)

int T,n;

struct point

{

    double x,y;

};

double xmult(point p1,point p2,point p0)

{

    return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

}

double distance(point p1,point p2)

{

    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));

}

point intersection(point u1,point u2,point v1,point v2)

{

    point ret=u1;

    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))

            /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));

    ret.x+=(u2.x-u1.x)*t;

    ret.y+=(u2.y-u1.y)*t;

    return ret;

}

point ptoseg(point p,point l1,point l2)

{

    point t=p; t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;

    if(xmult(l1,t,p)*xmult(l2,t,p)>eps)

        return distance(p,l1)<distance(p,l2)?l1:l2;

    return intersection(p,t,l1,l2);

}

point p[];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);

    double ans = 99999999999999.0;

    for(int i=;i<=n;i++)

    {

        int A = i-;

        int B = i;

        int C = i+;

        if(i-==) A=n;

        if(i+==n+) C=;

        point a,b;

        a.x = (p[A].x+p[B].x)/;

        a.y = (p[A].y+p[B].y)/;

        b.x = (p[C].x+p[B].x)/;

        b.y = (p[C].y+p[B].y)/;

        point c = ptoseg(p[B],a,b);

        ans = min(ans,distance(p[B],c));

    }

    printf("%f\n",ans);

    return ;

}