Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 6425 Accepted
Submission(s): 3099
1 struct Point{
2 double x,y;
3 };
4 struct Line{
5 Point p1,p2;
6 };
7 double Max(double a,double b)
8 {
9 return a>b?a:b;
10 }
11 double Min(double a,double b)
12 {
13 return a<b?a:b;
14 }
15 double xmulti(Point p1,Point p2,Point p0)
16 {
17 return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
18 }
19 bool inter(Line l1,Line l2)
20 {
21 if( Min(l2.p1.x,l2.p2.x)<=Max(l1.p1.x,l1.p2.x) &&
22 Min(l2.p1.y,l2.p2.y)<=Max(l1.p1.y,l1.p2.y) &&
23 Min(l1.p1.x,l1.p2.x)<=Max(l2.p1.x,l2.p2.x) &&
24 Min(l1.p1.y,l1.p2.y)<=Max(l2.p1.y,l2.p2.y) &&
25 xmulti(l1.p1,l2.p2,l2.p1)*xmulti(l1.p2,l2.p2,l2.p1)<=0 &&
26 xmulti(l2.p1,l1.p2,l1.p1)*xmulti(l2.p2,l1.p2,l1.p1)<=0 )
27 return true;
28 else
29 return false;
30 }
1 #include <iostream>
2 using namespace std;
3 struct Point{
4 double x,y;
5 };
6 struct Line{
7 Point p1,p2;
8 };
9 double Max(double a,double b)
10 {
11 return a>b?a:b;
12 }
13 double Min(double a,double b)
14 {
15 return a<b?a:b;
16 }
17 double xmulti(Point p1,Point p2,Point p0)
18 {
19 return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
20 }
21 bool inter(Line l1,Line l2)
22 {
23 if( Min(l2.p1.x,l2.p2.x)<=Max(l1.p1.x,l1.p2.x) &&
24 Min(l2.p1.y,l2.p2.y)<=Max(l1.p1.y,l1.p2.y) &&
25 Min(l1.p1.x,l1.p2.x)<=Max(l2.p1.x,l2.p2.x) &&
26 Min(l1.p1.y,l1.p2.y)<=Max(l2.p1.y,l2.p2.y) &&
27 xmulti(l1.p1,l2.p2,l2.p1)*xmulti(l1.p2,l2.p2,l2.p1)<=0 &&
28 xmulti(l2.p1,l1.p2,l1.p1)*xmulti(l2.p2,l1.p2,l1.p1)<=0 )
29 return true;
30 else
31 return false;
32 }
33 int main()
34 {
35 int N;
36 Line l[105];
37 while(cin>>N){
38 if(N==0) break;
39 for(int i=1;i<=N;i++)
40 cin>>l[i].p1.x>>l[i].p1.y>>l[i].p2.x>>l[i].p2.y;
41 int c = 0;
42 for(int i=1;i<=N-1;i++)
43 for(int j=i+1;j<=N;j++)
44 if(inter(l[i],l[j]))
45 c++;
46 cout<<c<<endl;
47 }
48 return 0;
49 }
Freecode : www.cnblogs.com/yym2013
hdu 1086:You can Solve a Geometry Problem too(计算几何,判断两线段相交,水题)
原文:http://www.cnblogs.com/yym2013/p/3539371.html