判断两直线是否相交 hdu1086

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 struct line
 7 {
 8     double x1;
 9     double y1;
10     double x2;
11     double y2;
12 }l[110];
13 
14 bool test(int i,int j)
15 {
16     int s=0;
17     double acd = (l[j].x1-l[i].x1)*(l[j].y1-l[j].y2) - (l[j].x1-l[j].x2)*(l[j].y1-l[i].y1);
18     double bcd = (l[j].x1-l[i].x2)*(l[j].y1-l[j].y2) - (l[j].x1-l[j].x2)*(l[j].y1-l[i].y2);
19     if(acd*bcd<=0)
20         s++;
21     double abd = (l[i].x1-l[j].x1)*(l[i].y1-l[i].y2) - (l[i].x1-l[i].x2)*(l[i].y1-l[j].y1);
22     double abc = (l[i].x1-l[j].x2)*(l[i].y1-l[i].y2) - (l[i].x1-l[i].x2)*(l[i].y1-l[j].y2);
23     if(abd*abc<=0)
24         s++;
25     if(s==2)
26         return true;
27     return false;
28 }
29 
30 int main()
31 {
32     int n;
33     while(scanf("%d",&n)!=EOF)
34     {
35         if(n==0)
36             break;
37         for(int i=0;i<n;i++)
38         {
39             scanf("%lf%lf%lf%lf",&l[i].x1,&l[i].y1,&l[i].x2,&l[i].y2);
40         }
41         int ans=0;
42         for(int i=0;i<n-1;i++)
43         {
44             for(int t=i+1;t<n;t++)
45             {
46                 if(test(i,t))
47                     ans++;
48             }
49         }
50         cout<<ans<<endl;
51     }
52     return 0;
53 }
View Code