fork download
  1. #include <iostream>
  2. #include <cmath>
  3. #define E 1e-5
  4. using namespace std;
  5.  
  6. double length(double x1, double y1, double x2, double y2){
  7. return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  8. }
  9.  
  10. bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){
  11. return (
  12. abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E
  13. &&
  14. abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E
  15. );
  16. }
  17.  
  18. bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
  19. return(
  20. abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E
  21. ||
  22. abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E
  23. ||
  24. abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E
  25. ||
  26. abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E
  27. );
  28. }
  29.  
  30. int main() {
  31. long x1, y1, x2, y2, x3, y3, x4, y4;
  32. double x, y;
  33. cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
  34. long long ky1, kx1, b1, ky2, kx2, b2;
  35. ky1 = y2 - y1;
  36. ky2 = y4 - y3;
  37. kx1 = x2 - x1;
  38. kx2 = x4 - x3;
  39. b1 = x1 * y2 - x2 * y1;
  40. b2 = x3 * y4 - x4 * y3;
  41. (kx1 * ky2 == kx2 * ky1) && (
  42. (
  43. b1 * ky2 != b2 * ky1
  44. &&
  45. b1 * kx2 != b2 * kx1
  46. ) && (cout << "No")
  47. || (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) && (cout << "Yes")
  48. || (cout << "No")
  49. ) || (
  50. y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1),
  51. x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1),
  52. (is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) && (cout << "Yes")
  53. || (cout << "No")
  54. );
  55. return 0;
  56. }
Success #stdin #stdout 0s 15240KB
stdin
1 0
0 1
0 0
1 1
stdout
Yes