ZOJ1648 Circuit Board（线段相交）

裸的判断线段相交
 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define eps 1e-12
16 #define MAXN 2005
17 #define INF 1000000007
18 #define MAX(a,b) (a > b ? a : b)
19 #define MIN(a,b) (a < b ? a : b)
20 #define mem(a) memset(a,0,sizeof(a))
21 
22 struct Point{
23     double x,y;
24     Point(double x=0, double y=0):x(x),y(y){}
25 };
26 
27 double Cross(Point A, Point B) { return A.x*B.y - A.y*B.x;}//叉积
28 
29 int N;
30 struct LINE
31 {
32     Point s, e;
33 } Line[MAXN];
34 
35 int main()
36 {
37     while(~scanf("%d", &N))
38     {
39         for(int i=0;i<N;i++)
40         {
41             scanf("%lf%lf%lf%lf", &Line[i].s.x, &Line[i].s.y, &Line[i].e.x, &Line[i].e.y);
42         }
43         int ok = 1;
44         for(int i=0;i<N && ok;i++)
45         {
46             Point Pi = Point(Line[i].e.x-Line[i].s.x, Line[i].e.y-Line[i].s.y);
47             for(int j=i+1;j<N && ok; j++)
48             {
49                 double c1 = Cross(Point(Line[j].s.x-Line[i].s.x, Line[j].s.y-Line[i].s.y), Pi);
50                 double c2 = Cross(Point(Line[j].e.x-Line[i].s.x, Line[j].e.y-Line[i].s.y), Pi);
51                 if(c1 * c2 < 0)
52                 {
53                     Point Pj = Point(Line[j].e.x-Line[j].s.x, Line[j].e.y-Line[j].s.y);
54                     c1 = Cross(Point(Line[i].s.x-Line[j].s.x, Line[i].s.y-Line[j].s.y), Pj);
55                     c2 = Cross(Point(Line[i].e.x-Line[j].s.x, Line[i].e.y-Line[j].s.y), Pj);
56                     if (c1 * c2 < 0) ok = 0;
57                 }
58             }
59         }
60         printf("%s
",ok?"ok!":"burned!");
61     }
62     return 0;
63 }