首页 > 代码库 > CodeForces 772B Volatile Kite

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[2000];int main(){        scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);    double ans = 99999999999999.0;    for(int i=1;i<=n;i++)    {        int A = i-1;        int B = i;        int C = i+1;        if(i-1==0) A=n;        if(i+1==n+1) C=1;        point a,b;        a.x = (p[A].x+p[B].x)/2;        a.y = (p[A].y+p[B].y)/2;        b.x = (p[C].x+p[B].x)/2;        b.y = (p[C].y+p[B].y)/2;        point c = ptoseg(p[B],a,b);        ans = min(ans,distance(p[B],c));    }    printf("%f\n",ans);        return 0;}

 

CodeForces 772B Volatile Kite