USACO Section 5.2 Electric Fences - 有意思的枚举+计算几何

网友投稿 263 2022-08-25

USACO Section 5.2 Electric Fences - 有意思的枚举+计算几何

这题一上来首先想到的是能否用数学方法来求得这个点..比如说画一个半径最小的圆使其与所有线段相交或相切…那么圆心就是所求..想法似乎没问题..但怎么来求是毫无头绪~想了良久也没想出用数学的方法如何实现…

还是用枚举了…题目范围不大..并且精度要求不高..将整个( 0 , 0 ) ~ ( 100 ,100 ) 的连续空间离散分成1000个每个相距0.1的点..枚举每个点..定能找到答案..复杂度是 N*O(100^2)…估计最大数据时间大概需要十秒..发现这个时间是可以有优化空间的…我就直接用二分了..每次枚举9个点 ( 正方形平均的9个点 )…找到最有点后再以这个点为九个点的中心点缩小步长再尝试9个点..直道枚举的两点间相差<0.01..也就是步长<0.01…

还有很重要的一个问题..枚举了一个点如何求出其到某线段的最短距离?..要分两种情况..第一种是这个点做垂线会落到这个线段上…这种情况用差乘求出这个点与线段构成的三角形面积*2…然后再除以这个线段的长度就是垂线的长度…而第二种情况是这个点对线段做出的垂线在线段外..那么最短的距离只可能是到线段两个端点距离的最短那个..如何判断这两种情况…其实出现第二种情况是因为这个点与线段构成的三角形是钝角三角形..并且不是这个点的两侧是钝角..是另外两个角有一个是钝角..如何判断钝角三角形..先求出三条边的长度..都知道坐标这个很好求…当x1^2+x2^2

Program:

/* ID: zzyzzy12 LANG: C++ TASK: fence3*/ #include #include #include #include #include #include#include#include #include #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std;struct node{ double x0,y0,x1,y1,len; }line[152];int i,n;double x,y,ansx,ansy,ans,now,MaxX,MaxY,StartX,StartY,len,step; double dis(node a){ double x1,y1,x2,y2; x1=(x-a.x0)*(x-a.x0)+(y-a.y0)*(y-a.y0); x2=(x-a.x1)*(x-a.x1)+(y-a.y1)*(y-a.y1); if (x1-x2-a.len*a.len>-0.001 || x2-x1-a.len*a.len>-0.001) { if (x1MaxX) MaxX=line[i].x1; if (line[i].x0MaxY) MaxY=line[i].y1; if (line[i].y0MaxX) len=MaxY/2; else len=MaxX/2; ans=oo; ans*=ans; while (len>0.01) { step=len/4; MaxX=StartX+len; MaxY=StartY+len; for (x=StartX;x<=MaxX;x+=step) for (y=StartY;y<=MaxY;y+=step) { now=0; for (i=1;i<=n;i++) { now+=dis(line[i]); if (now>ans) break; } if (now

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：数据
上一篇:销售员的朋友圈应当发些什么内容！（做销售发些什么朋友圈）
下一篇:POJ-1947 简单的树型DP,但要考虑完全
相关文章

 发表评论

暂时没有评论，来抢沙发吧~