首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。