判断线段与线段相交
莫名其妙的数据量
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cmath> 5 #include <cstring> 6 using namespace std; 7 const double eps = 1e-8; 8 int dcmp(double x) 9 { 10 return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1); 11 } 12 struct Point 13 { 14 double x,y; 15 Point(double a = 0, double b = 0) : x(a), y(b) {} 16 }; 17 Point operator - (Point a, Point b) 18 { 19 return Point(a.x-b.x, a.y-b.y); 20 } 21 double Det(Point a, Point b) 22 { 23 return a.x * b.y - a.y * b.x; 24 } 25 double Dot(Point a, Point 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(Det(a1 - p, a2 - p)) == 0 && dcmp(Dot(a1 - p, a2 - p)) <= 0; 32 } 33 bool SegCross(Point a1, Point a2, Point b1, Point b2) 34 { 35 double c1 = Det(a2 - a1, b1 - a1); 36 double c2 = Det(a2 - a1, b2 - a1); 37 double c3 = Det(b2 - b1, a1 - b1); 38 double c4 = Det(b2 - b1, a2 - b1); 39 if (dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0) return 1; 40 else if (OnSegment(b1, a1, a2) ) return 1; 41 else if (OnSegment(b2, a1, a2) ) return 1; 42 else if (OnSegment(a1, b1, b2) ) return 1; 43 else if (OnSegment(a2, b1, b2) ) return 1; 44 else return 0; 45 } 46 47 struct Line 48 { 49 Point s,e; 50 Line() {} 51 Line(Point a,Point b) : s(a), e(b) {} 52 }l[100005]; 53 int res[1005]; 54 int main() 55 { 56 int n; 57 while (~scanf("%d", &n) && n) 58 { 59 for (int i = 1; i <= n; i++){ 60 scanf("%lf%lf%lf%lf", &l[i].e.x, &l[i].e.y, &l[i].s.x, &l[i].s.y); 61 } 62 int cnt = 0; 63 for(int i = 1; i <= n; i++) 64 { 65 bool flag = 1; 66 for (int j = i+1; j <= n; j++) 67 { 68 if(SegCross(l[i].e, l[i].s, l[j].e, l[j].s)){ 69 flag = 0; break; 70 } 71 } 72 if(flag) res[cnt++] = i; 73 } 74 75 printf("Top sticks: "); 76 for (int i = 0; i < cnt-1; i++) 77 printf("%d, ", res[i]); 78 printf("%d. ", res[cnt-1]); 79 } 80 }