判断线段两两相交的个数
打模板熟练程度++；
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 using namespace std; 5 const double EPS = 1e-10; 6 struct Point 7 { 8 double x,y; 9 Point(){} 10 Point(double x1,double y1):x(x1),y(y1) {} 11 }a[105],b[105]; 12 typedef Point Vect; 13 Vect operator - (Vect A, Vect B) 14 { 15 return Vect(A.x - B.x, A.y - B.y); 16 } 17 int dcmp(double x) 18 { 19 return fabs(x) < EPS ? 0 : (x < 0? -1: 1); 20 } 21 double Cross(Vect A, Vect B) 22 { 23 return A.x * B.y - A.y * B.x; 24 } 25 double Dot(Vect A, Vect B) 26 { 27 return A.x * B.x + A.y * B.y; 28 } 29 bool OnSegment(Point p, Point a1, Point a2) 30 { 31 return dcmp(Cross(a1 - p, a2 - p)) == 0 && dcmp( Dot(a1 - p, a2 - p) ) <= 0; 32 } 33 34 bool SegmentIntersection(Point a1, Point a2, Point b1, Point b2) 35 { 36 double c1 = Cross(a2 - a1, b1 - a1); 37 double c2 = Cross(a2 - a1, b2 - a1); 38 double c3 = Cross(b2 - b1, a1 - b1); 39 double c4 = Cross(b2 - b1, a2 - b1); 40 if(dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0) return 1; 41 else if(OnSegment(b1, a1, a2) ) return 1; 42 else if(OnSegment(b2, a1, a2) ) return 1; 43 else if(OnSegment(a1, b1, b2) ) return 1; 44 else if(OnSegment(a2, b1, b2) ) return 1; 45 else return 0; 46 } 47 48 int main() 49 { 50 int n; 51 while(~scanf("%d",&n) && n) 52 { 53 for(int i = 1; i <= n; i++) 54 scanf("%lf%lf%lf%lf", &a[i].x, &a[i].y, &b[i].x, &b[i].y); 55 int ans = 0; 56 for(int i = 1; i <= n; i++) 57 for(int j = i + 1; j <= n; j++) 58 if(SegmentIntersection(a[i], b[i], a[j], b[j])) 59 ans++; 60 printf("%d ", ans); 61 } 62 }