POJ 3304 Segments

------------------------------------------------------------------------------------------------------

由于几乎没写过计算几何只要$WA$了第一反应是调$eps$ 然而这题坑点并不是调$eps$

对于一条直线是否穿过一条线段如果线段比较短的话只要看看线段两端点是否都贴在直线旁就好

然而如果直线的方向向量由两个非常接近的点确定那么与其他的向量做叉积的时候几乎都是$0$

所以我们枚举确定直线方向的两端点的时候要把这一种情况跳过

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 const double eps = 1e-8;
 7 const int N = 110;
 8 struct node
 9 {
10     double x, y;
11 }a[N << 1];
12 int t, n, n2;
13 double cross(node &aa, node &bb, node &cc)
14 {
15     return (bb.x - aa.x) * (cc.y - aa.y) - (cc.x - aa.x) * (bb.y - aa.y);
16 }
17 bool check(node &aa, node &bb, node &cc, node &dd)
18 {
19     double t1, t2;
20     t1 = cross(aa, bb, cc);
21     t2 = cross(aa, bb, dd);
22     return (t1 <= eps && t2 >= -eps) || (t1 >= -eps && t2 <= eps);
23 }
24 int main()
25 {
26     scanf("%d", &t);
27     while(t--)
28     {
29         scanf("%d", &n);
30         for(int i = 1; i <= n; ++i)
31             scanf("%lf%lf%lf%lf", &a[i * 2 - 1].x, &a[i * 2 -1].y,
32              &a[i * 2].x, &a[i * 2].y);
33         n2 = n << 1;
34         bool gain = 0;
35         for(int i = 1; i < n2 && !gain; ++i)
36             for(int j = i + 1; j <= n2 && !gain; ++j)
37             {
38                 if(abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y) < eps * 2)
39                     continue;
40                 for(int k = 1; k < n2; k += 2)
41                     if(!check(a[i], a[j], a[k], a[k + 1]))
42                          break;
43                     else if(k == n2 - 1)
44                     {
45                         gain = 1 ;
46                         break;
47                     }
48             }
49         if(gain)
50             puts("Yes!");
51         else
52             puts("No!");
53     }
54     return 0;
55 }