poj 3304 Segments

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #define N 1000005
 5 #define LL long long
 6 #define inf 0x3f3f3f3f
 7 #define eps 1e-8
 8 using namespace std;
 9 inline int ra()
10 {
11     int x=0,f=1; char ch=getchar();
12     while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
13     while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
14     return x*f;
15 }
16 int T,n;
17 bool flag;
18 struct point{double x,y;};
19 struct seg{point a,b;}s[105];
20 point sub(point a, point b)   //b->a
21 {   
22     point t; t.x=a.x-b.x; t.y=a.y-b.y; return t;
23 }
24 double cross(point a, point b)
25 {
26     return a.x*b.y-a.y*b.x;
27 }
28 double turn(point p1, point p2, point p3)
29 {
30     return cross(sub(p2,p1),sub(p3,p1));
31 }
32 bool sgn(double x, double y)
33 {
34     if (fabs(x-y)<eps) return 0; else return 1;
35 }
36 bool jud(point a, point b)
37 {
38     if (sgn(a.x,b.x)==0 && sgn(a.y,b.y)==0) return 0;
39     for (int i=1; i<=n; i++)
40         if (turn(a,b,s[i].a)*turn(a,b,s[i].b)>eps) return 0;
41     return 1;
42 }
43 int main()
44 {
45     T=ra();
46     while (T--)
47     {
48         n=ra();
49         for (int i=1; i<=n; i++) scanf("%lf%lf%lf%lf",&s[i].a.x,&s[i].a.y,&s[i].b.x,&s[i].b.y);
50         flag=0;
51         for (int i=1; i<=n; i++)
52             if (!flag) 
53                 for (int j=1; j<=n; j++)
54                 {
55                     if (jud(s[i].a,s[j].a) || jud(s[i].a,s[j].b) || jud(s[i].b,s[j].a) || jud(s[i].b,s[j].b)) 
56                     {
57                         flag=1;
58                         break;
59                     }
60                 } 
61         if (!flag) printf("No!\n");
62         else puts("Yes!");
63     }
64     return 0;
65 }