POJ 3304 Segments
8859 ワード
テーマリンク:http://poj.org/problem?id=3304
------------------------------------------------------
計算幾何学はほとんど書いていませんので、WA$だけです。第一反応は$epsです。しかし、この問題点は$epsではありません。
直線が線分を通っているかどうかは線分が短いなら、線分の両端の点を見てください。全部直線に貼ってあるかどうかだけでいいです。
しかし、直線の方向ベクトルが二つの非常に近い点から決定されると、他のベクトルとフォーク積するときはほとんど$0です。
ですから、直線方向の両端の点を決める時はこのような状況をスキップします。
------------------------------------------------------
計算幾何学はほとんど書いていませんので、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 }