学步园

网上很多人给出了解题思路的了，自己也是根据大牛们的思路做了，小弟很少做计算几何的问题，因为这道题涉及到比较严格的精度控制的问题，所以记录一下以备自己以后复习查看。。

思路（都是转载别人的）：

首先题中的要求等价于：存在一条直线l和所有的线段都相交。
证明：若存在一条直线l和所有线段相交，作一条直线m和l垂直，则m就是题中要求的直线，所有线段投影的一个公共点即为垂足。（l和每条线段的交点沿l投影到m上的垂足处）
反过来，若存在m，所有线段在m上的投影有公共点，则过这点垂直于m作直线l，l一定和所有线段相交。

然后证存在l和所有线段相交等价于存在l过某两条线段的各一个端点且和所有线段相交。
充分性显然。必要性：若有l和所有线段相交，则可保持l和所有线段相交，左右平移l到和某一线段交于端点停止（“移不动了”）。然后绕这个交点旋转。也是转到“转不动了”（和另一线段交于其一个端点）为止。这样就找到了一个新的l。
于是本题可归结为枚举两两线段的各一个端点，连一条直线，再判断剩下的线段是否都和这条直线有交点。

在discuss有人给出两个容易出错的地方，自己错了两次，但根据这里一改就ac了
1.需要考虑当n=1的情况，当然n=1和2都是Yes。
2.在枚举所有顶点的时候考虑一下顶点的距离小于1.0*10^(-8)时是不用考虑的。

#include <cstdio><br /> #include <cmath><br /> #define eps 1e-8<br /> #define zero(x) (((x)>0?(x):-(x))<eps)<br /> #define _sign(x) ((x)>eps?1:((x)<-eps?2:0))<br /> #define N 200</p> <p>struct point{double x,y;};</p> <p>point sg[N];<br /> int n;</p> <p>double xmult(point p1,point p2,point p0){<br /> return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);<br /> }<br /> //判两点在线段异侧,点在线段上返回0,l1, l2 是直线<br /> // 异侧(相交)1， 同侧(不相交)0<br /> int opposite_side(point p1,point p2,point l1,point l2){<br /> return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps;<br /> }</p> <p>double distance(point p1,point p2){<br /> return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));<br /> }</p> <p>int canfind(int i, int j) { // 如果找到那条直线返回1<br /> for(int k = 0; k < n; k += 2){<br /> if(k/2==i/2 || k/2==j/2) continue; // 所选线段跟直线两点所在线段相同就不用管了<br /> if(_sign(xmult(sg[i], sg[j], sg[k]))==0 || _sign(xmult(sg[i],sg[j],sg[k+1]))==0)<br /> continue; // 线段跟点在直线上<br /> if(opposite_side(sg[k], sg[k+1], sg[i], sg[j])==0)<br /> return 0;<br /> }<br /> return 1;<br /> }</p> <p>int findline(){<br /> for(int i = 0; i < n; ++i) {<br /> for(int j = i+1; j < n; ++j){<br /> if(i/2==j/2) continue; // 形成直线的点是在同一条线段就不用理<br /> if(zero(distance(sg[i], sg[j]))) // 顶点的距离小于1.0*10^(-8)时是不用考虑的<br /> continue;<br /> if(canfind(i, j)) return 1;<br /> }<br /> }<br /> return 0;<br /> }</p> <p>int main() {<br /> int t;<br /> scanf("%d", &t);<br /> while(t--) {<br /> scanf("%d", &n);<br /> n *= 2;<br /> for(int i = 0; i < n; ++i) {<br /> scanf("%lf%lf", &sg[i].x, &sg[i].y);<br /> }<br /> if(n <= 2) {<br /> printf("Yes!/n");<br /> } else {<br /> int ans = findline();<br /> printf("%s!/n", ans ? "Yes" : "No");<br /> }<br /> }<br /> return 0;<br /> }