line_segment_intersection_2190.cpp (1244B)
1 #include <algorithm> 2 #include <iostream> 3 4 bool inran(long long int a, long long int b, long long int m) { 5 return m >= std::min(a, b) && m <= std::max(a, b); 6 } 7 8 bool inseg(long long int d, long long int dt, long long int du) { 9 return dt >= 0 && dt <= d && du >= 0 && du <= d; 10 } 11 12 bool f(long long int x1, long long int y1, long long int x2, long long int y2, 13 long long int x3, long long int y3, long long int x4, long long int y4) { 14 long long int xt = x2-x1, yt = y2-y1; 15 long long int xu = x4-x3, yu = y4-y3; 16 long long int d = xt * (-yu) - yt * (-xu); 17 long long int dt = (x3-x1) * (-yu) - (y3-y1) * (-xu); 18 long long int du = (xt) * (y3-y1) - (yt) * (x3-x1); 19 20 if (d == 0) { 21 // Parallel on different lines 22 if (dt != 0 || du != 0) return false; 23 24 // Parallel, same line 25 return xt == 0 ? 26 inran(y1,y2,y3) || inran(y1,y2,y4) || inran(y3,y4,y1) : 27 inran(x1,x2,x3) || inran(x1,x2,x4) || inran(x3,x4,x1); 28 } else { 29 // Not parallel 30 long long int m = d > 0 ? 1 : -1; 31 return inseg(m*d, m*dt, m*du); 32 } 33 } 34 35 int main() { 36 long long int x1, y1, x2, y2, x3, y3, x4, y4; 37 int n; 38 std::cin >> n; 39 while (std::cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4) 40 std::cout << (f(x1,y1,x2,y2,x3,y3,x4,y4) ? "YES\n" : "NO\n"); 41 }