Advertisement
Tbl_Mne_Ne_Dryg

Untitled

Dec 6th, 2022
606
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.57 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5. using ld = long double;
  6. const ld EPS = 0.1;
  7.  
  8. // A <= B
  9. //
  10.  
  11. class point {
  12. public:
  13.   ld x, y;
  14.   point() = default;
  15.   point(ld x, ld y) {
  16.     this->x = x;
  17.     this->y = y;
  18.   }
  19. };
  20.  
  21. bool operator == (point A, point B) {
  22.   return abs(A.x - B.x) < EPS && abs(A.y - B.y) < EPS;
  23. }
  24.  
  25. class line {
  26. public:
  27.   ld A, B, C;
  28.   line() = default;
  29.   line(point a, point b) {
  30.     A = a.y - b.y;
  31.     B = b.x - a.x;
  32.     C = - A * a.x - B * a.y;
  33.   }
  34.   bool in(point x) const {
  35.     return abs(A * x.x + B * x.y + C) < EPS;
  36.   }
  37. };
  38.  
  39. class segment {
  40. public:
  41.   point a, b;
  42.   segment() = default;
  43.   segment(point a, point b) {
  44.     this->a = a;
  45.     this->b = b;
  46.   }
  47.   bool in(point x) const {
  48.     if (a == b)
  49.       return x == a;
  50.     bool ch1 = (min(a.x, b.x) - x.x < EPS && x.x - max(a.x, b.x) < EPS) &&
  51.                (min(a.y, b.y) - x.y < EPS && x.y - max(a.y, b.y) < EPS);
  52.     bool ch2 = line(a, b).in(x);
  53.     return ch1 && ch2;
  54.   }
  55. };
  56.  
  57. class triangle {
  58. public:
  59.   point A, B, C;
  60.   triangle() = default;
  61.   triangle(point A, point B, point C) {
  62.     this->A = A;
  63.     this->B = B;
  64.     this->C = C;
  65.   }
  66. };
  67.  
  68.  
  69. ld dist(point a, point b) {
  70.   return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  71. }
  72.  
  73. ld S(triangle t) {
  74.   ld a = dist(t.A, t.B);
  75.   ld b = dist(t.B, t.C);
  76.   ld c = dist(t.A, t.C);
  77.   ld p = (a + b + c) / 2.0;
  78.   return sqrt(p * (p - a) * (p - b) * (p - c));
  79. }
  80.  
  81. bool in(point x, triangle t) {
  82.   ld S1 = S(t);
  83.   ld S2 = S({x, t.A, t.B}) + S({x, t.B, t.C}) + S({x, t.A, t.C});
  84.   bool ch1 = abs(S1 - S2) < EPS;
  85.   bool ch2 = segment(t.A, t.C).in(x);
  86.   bool ch3 = segment(t.A, t.B).in(x);
  87.   bool ch4 = segment(t.C, t.B).in(x);
  88.   return ch1 || ch2 || ch3 || ch4;
  89. }
  90.  
  91. ld det(ld a, ld b, ld c, ld d) {
  92.   return a * d - b * c;
  93. }
  94.  
  95. pair<bool, point> intersect(line n, line m) {
  96.   ld zn = det(m.A, m.B, n.A, n.B);
  97.   if (abs(zn) < EPS)
  98.     return {false, point()};
  99.   point res;
  100.   res.x = -det(m.C, m.B, n.C, n.B) / zn;
  101.   res.y = -det(m.A, m.C, n.A, n.C) / zn;
  102.   return {true, res};
  103. }
  104.  
  105. bool intersect(segment a, segment b) {
  106.   line la(a.a, a.b);
  107.   line lb(b.a, b.b);
  108.   auto inter = intersect(la, lb);
  109.   if (!inter.first)
  110.     return false;
  111.   return a.in(inter.second) && b.in(inter.second);
  112. }
  113.  
  114. signed main() {
  115.   ios::sync_with_stdio(false);
  116.   cin.tie(0);
  117. #ifdef LOCAL
  118.   freopen("input", "r", stdin);
  119. #endif
  120.   //cout << "YES\n";
  121.   //return 0;
  122.   int x1, y1, a1, b1, x2, y2, a2, b2;
  123.   cin >> x1 >> y1 >> a1 >> b1 >> x2 >> y2 >> a2 >> b2;
  124.   point A1(x1, y1);
  125.   point B1(x1 + a1, y1);
  126.   point C1(x1, y1 + b1);
  127.   point A2(x2, y2);
  128.   point B2(x2 + a2, y2);
  129.   point C2(x2, y2 + b2);
  130.   triangle t1(A1, B1, C1), t2(A2, B2, C2);
  131.   bool ans = false;
  132.   ans |= in(A2, t1);
  133.   ans |= in(B2, t1);
  134.   ans |= in(C2, t1);
  135.   ans |= in(A1, t2);
  136.   ans |= in(B1, t2);
  137.   ans |= in(C1, t2);
  138.  
  139.   if (!((t1.A == t1.B && t1.B == t1.C) || (t2.A == t2.B && t2.B == t2.C))) {
  140.     ans |= intersect(segment(t1.A, t1.B), segment(t2.A, t2.B));
  141.     ans |= intersect(segment(t1.A, t1.C), segment(t2.A, t2.B));
  142.     ans |= intersect(segment(t1.B, t1.C), segment(t2.A, t2.B));
  143.  
  144.     ans |= intersect(segment(t1.A, t1.B), segment(t2.A, t2.C));
  145.     ans |= intersect(segment(t1.A, t1.C), segment(t2.A, t2.C));
  146.     ans |= intersect(segment(t1.B, t1.C), segment(t2.A, t2.C));
  147.  
  148.     ans |= intersect(segment(t1.A, t1.B), segment(t2.B, t2.C));
  149.     ans |= intersect(segment(t1.A, t1.C), segment(t2.B, t2.C));
  150.     ans |= intersect(segment(t1.B, t1.C), segment(t2.B, t2.C));
  151.   }
  152.   cout << (ans ? "YES\n" : "NO\n");
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement