Advertisement
welleyth

Geometry

Jun 7th, 2022
852
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.33 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. #define int long long
  8. #define mp make_pair
  9. #define pb push_back
  10.  
  11. #pragma GCC optimize("Ofast")
  12. #pragma GCC optimize("unroll-loops")
  13.  
  14. constexpr int INF = (int)1e18;
  15. constexpr int N = (int)1e5 + 111;
  16. constexpr int md = (int)1e9+7;
  17. constexpr int mdPower = (int)1e9+7 - 1;
  18.  
  19. mt19937 rnd(time(nullptr));
  20.  
  21. void add(int& a,int b){
  22.     a += b; if(a >= md) a -= md;
  23. }
  24. void sub(int& a,int b){
  25.     a -= b; while(a < 0) a += md;
  26. }
  27. void add(__int128& a,int b){
  28.     a += b;
  29. }
  30. void sub(__int128& a,int b){
  31.     a -= b;
  32. }
  33.  
  34. int bpow(int a,int b){
  35.     if(b == 0)
  36.         return 1;
  37.     if(b % 2 == 0){
  38.         int t = bpow(a,b>>1);
  39.         return t*t%md;
  40.     }
  41.     return a*bpow(a,b-1) % md;
  42. }
  43.  
  44. int inv(int a){
  45.     return bpow(a,md-2);
  46. }
  47.  
  48. int fac[N],invfac[N];
  49.  
  50. void init(){
  51.     fac[0] = 1;
  52.     for(int i = 1; i < N; i++){
  53.         fac[i] = (fac[i-1] * i) % md;
  54.     }
  55.     invfac[N-1] = inv(fac[N-1]);
  56.     for(int i = N-2; i >= 0; i--){
  57.         invfac[i] = (invfac[i+1] * (i+1))%md;
  58.     }
  59.     return;
  60. }
  61.  
  62. int C(int n,int k){
  63.     return fac[n] * invfac[k] % md * invfac[n-k] % md;
  64. }
  65.  
  66. struct pt{
  67.     double x,y;
  68.     pt(){}
  69.     pt(int x,int y):x(x),y(y){}
  70.     pt(double x,double y):x(x),y(y){}
  71. };
  72.  
  73. struct Line{ /// ax + by + c = 0
  74.     int a,b,c;
  75.     Line(){}
  76.     Line(int a,int b,int c):a(a),b(b),c(c){}
  77.     Line(pt p1,pt p2){
  78.         a = p2.y - p1.y;
  79.         b = p1.x - p2.x;
  80.         c = p2.x*p1.y - p1.x*p2.y;
  81.         int g = __gcd(a,__gcd(b,c));
  82.         a /= g;
  83.         b /= g;
  84.         c /= g;
  85.     }
  86. };
  87.  
  88. bool operator==(Line L1,Line L2){
  89.     return L1.a == L2.a && L1.b == L2.b && L1.c == L2.c;
  90. }
  91. bool operator==(pt a,pt b){
  92.     return a.x == b.x && a.y == b.y;
  93. }
  94.  
  95. pt AreTheSame = pt(INF,INF);
  96. pt NoInterSection = pt(-INF,-INF);
  97.  
  98. //pt GetIntersection(Line L1,Line L2){
  99. //    if(L1 == L2)
  100. //        return AreTheSame;
  101. //    /**
  102. //    a1*x + b1*y + c1 = 0
  103. //    a2*x + b2*y + c2 = 0
  104. //
  105. //    k = a2/a1,
  106. //
  107. //    b2 -= k*b1
  108. //    c2 -= k*c1
  109. //    k = b1/b2
  110. //    **/
  111. //    int a1,a2,b1,b2,c1,c2;
  112. //    a1 = L1.a, b1 = L1.b, c1 = L1.c;
  113. //    a2 = L2.a, b2 = L2.b, c2 = L2.c;
  114. //    int d = a1 * b2 - a2 * b1;
  115. //    if(d == 0)
  116. //        return NoInterSection;
  117. //    int dx = c1*b2-c2*b1;
  118. //    int dy = a1*c2-a2*c1;
  119. //    return pt(-1.0*dx/d,-1.0*dy/d);
  120. //}
  121.  
  122. inline int area (pt a, pt b, pt c) {
  123.     return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  124. }
  125. inline bool intersect_1 (int a, int b, int c, int d) {
  126.     if (a > b)  swap (a, b);
  127.     if (c > d)  swap (c, d);
  128.     return max(a,c) <= min(b,d);
  129. }
  130.  
  131. bool intersect (pt a, pt b, pt c, pt d) {
  132.     return intersect_1 (a.x, b.x, c.x, d.x)
  133.         && intersect_1 (a.y, b.y, c.y, d.y)
  134.         && area(a,b,c) * area(a,b,d) <= 0
  135.         && area(c,d,a) * area(c,d,b) <= 0;
  136. }
  137.  
  138. struct Monogon{
  139.     vector<pt> dots;
  140.     int n;
  141.     Monogon(){}
  142.     void Read(){
  143.         int sz;
  144.         cin >> sz;
  145.         n = sz;
  146.         dots.resize(sz);
  147.         for(auto& p : dots){
  148.             int x,y;
  149.             cin >> x >> y;
  150.             p.x = x;
  151.             p.y = y;
  152. //            cin >> p.x >> p.y;
  153.         }
  154.         dots.pb(dots[0]);
  155.     }
  156.     bool LiesIn(pt& p){
  157.         pt p2 = pt(-(int)1e4-rnd()%111,-(int)1e4+(int)rnd()%1111);
  158.         int c = 0;
  159.         for(int i = 0; i + 1 < dots.size(); i++){
  160.             pt p21 = dots[i], p22 = dots[i+1];
  161.             c ^= intersect(p2,p,p21,p22);
  162.         }
  163.         return c == 1;
  164.     }
  165.     bool LiesIn(Monogon& b){
  166. //        bool ok = 1;
  167.         for(auto& p : b.dots){
  168.             if(!LiesIn(p)){
  169.                 return false;
  170.             }
  171.         }
  172.         return true;
  173.     }
  174.     bool HasIntersection(Monogon& b){
  175.         for(auto& p : b.dots){
  176.             if(LiesIn(p)){
  177. //                cerr << p.x << " " << p.y << "\n";
  178.                 return true;
  179.             }
  180.         }
  181.         return false;
  182.     }
  183. };
  184.  
  185. bool check(Monogon& a,Monogon& b){
  186.     if(a.HasIntersection(b) || b.HasIntersection(a))
  187.         return true;
  188.  
  189.     for(int i = 0; i + 1 < a.dots.size(); i++){
  190.         pt p11 = a.dots[i], p12 = a.dots[i+1];
  191.         for(int j = 0; j + 1 < b.dots.size(); j++){
  192.             pt p21 = b.dots[j], p22 = b.dots[j+1];
  193.             if(intersect(p11,p12,p21,p22)){
  194.                 return true;
  195.             }
  196.         }
  197.     }
  198.  
  199.     return false;
  200. }
  201.  
  202. void solve(){
  203. //    cerr << HasIntersection(pt(6ll,-1ll),pt(6ll,4ll),pt(0ll,0ll),pt(10ll,0ll)) << "\n";
  204. //    return;
  205.     Monogon a,b;
  206.  
  207.     a.Read(), b.Read();
  208.  
  209.     cout << (check(a,b) ? "YES" : "NO") << "\n";
  210.  
  211. //    Line L(pt(6,10.46),pt(6.65,10.69));
  212. //
  213. //    cout << fixed << setprecision(10) << L.a << " " << L.b << " " << L.c << "\n";
  214.  
  215.     return;
  216. }
  217.  
  218. signed main(){
  219.     ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  220.     int tests = 1;
  221.     cin >> tests;
  222.     for(int test = 1; test <= tests; test++){
  223. //        cerr << "test = " << test << "\n";
  224.         solve();
  225.     }
  226.     return 0;
  227. }
  228. /**
  229. (x-x1)/(x2-x1) = (y-y1)/(y2-y1)
  230.  
  231. (x-x1)*(y2-y1) = (y-y1)*(x2-x1)
  232. x*(y2-y1) - x1*(y2-y1) = y*(x2-x1) - y1*(x2-x1)
  233. x*(y2-y1) + y*(x1-x2) - x1*y2 + x1*y1 = y1*x1 - y1*x2
  234. x*(y2-y1) + y*(x1-x2) - x1*y2 + y1*x2 = 0
  235.  
  236. 1
  237. 3
  238. 0 -1
  239. 1 1
  240. -1 1
  241. 3
  242. 0 2
  243. -1 -2
  244. 1 -2
  245.  
  246. 2.85    3.12
  247. 8.932
  248. 2.4669
  249.  
  250. **/
  251.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement