Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8693 Accepted Submission(s): 4232
1 #include <iostream> 2 #include <cmath> 3 4 using namespace std; 5 6 struct POINT 7 { 8 double x; 9 double y; 10 }; 11 struct LINESEG 12 { 13 POINT s; 14 POINT e; 15 }; 16 17 double multiply(POINT a,POINT b,POINT c) 18 { 19 return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y)); 20 } 21 bool intersect(LINESEG u,LINESEG v) 22 { 23 return( (max(u.s.x,u.e.x)>=min(v.s.x,v.e.x))&& //排斥实验 24 (max(v.s.x,v.e.x)>=min(u.s.x,u.e.x))&& 25 (max(u.s.y,u.e.y)>=min(v.s.y,v.e.y))&& 26 (max(v.s.y,v.e.y)>=min(u.s.y,u.e.y))&& 27 (multiply(v.s,u.e,u.s)*multiply(u.e,v.e,u.s)>=0)&& //跨立实验 28 (multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)>=0)); 29 } 30 int main() 31 { 32 33 int N; 34 while(cin>>N&&N) 35 { 36 LINESEG A[101]; 37 int count=0; 38 for(int i=0;i<N;i++) 39 { 40 cin>>A[i].s.x>>A[i].s.y>>A[i].e.x>>A[i].e.y; 41 } 42 for(int i=0;i<N;i++) 43 for(int j=0;j<N;j++) 44 if(intersect(A[i],A[j])&&i!=j) 45 count++; 46 cout<<count/2<<endl; 47 } 48 return 0; 49 }
原文:http://www.cnblogs.com/bushuiqitiandi/p/4666767.html