Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- #define int long long
- #define mp make_pair
- #define pb push_back
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- constexpr int INF = (int)1e18;
- constexpr int N = (int)1e5 + 111;
- constexpr int md = (int)1e9+7;
- constexpr int mdPower = (int)1e9+7 - 1;
- mt19937 rnd(time(nullptr));
- void add(int& a,int b){
- a += b; if(a >= md) a -= md;
- }
- void sub(int& a,int b){
- a -= b; while(a < 0) a += md;
- }
- void add(__int128& a,int b){
- a += b;
- }
- void sub(__int128& a,int b){
- a -= b;
- }
- int bpow(int a,int b){
- if(b == 0)
- return 1;
- if(b % 2 == 0){
- int t = bpow(a,b>>1);
- return t*t%md;
- }
- return a*bpow(a,b-1) % md;
- }
- int inv(int a){
- return bpow(a,md-2);
- }
- int fac[N],invfac[N];
- void init(){
- fac[0] = 1;
- for(int i = 1; i < N; i++){
- fac[i] = (fac[i-1] * i) % md;
- }
- invfac[N-1] = inv(fac[N-1]);
- for(int i = N-2; i >= 0; i--){
- invfac[i] = (invfac[i+1] * (i+1))%md;
- }
- return;
- }
- int C(int n,int k){
- return fac[n] * invfac[k] % md * invfac[n-k] % md;
- }
- struct pt{
- double x,y;
- pt(){}
- pt(int x,int y):x(x),y(y){}
- pt(double x,double y):x(x),y(y){}
- };
- struct Line{ /// ax + by + c = 0
- int a,b,c;
- Line(){}
- Line(int a,int b,int c):a(a),b(b),c(c){}
- Line(pt p1,pt p2){
- a = p2.y - p1.y;
- b = p1.x - p2.x;
- c = p2.x*p1.y - p1.x*p2.y;
- int g = __gcd(a,__gcd(b,c));
- a /= g;
- b /= g;
- c /= g;
- }
- };
- bool operator==(Line L1,Line L2){
- return L1.a == L2.a && L1.b == L2.b && L1.c == L2.c;
- }
- bool operator==(pt a,pt b){
- return a.x == b.x && a.y == b.y;
- }
- pt AreTheSame = pt(INF,INF);
- pt NoInterSection = pt(-INF,-INF);
- //pt GetIntersection(Line L1,Line L2){
- // if(L1 == L2)
- // return AreTheSame;
- // /**
- // a1*x + b1*y + c1 = 0
- // a2*x + b2*y + c2 = 0
- //
- // k = a2/a1,
- //
- // b2 -= k*b1
- // c2 -= k*c1
- // k = b1/b2
- // **/
- // int a1,a2,b1,b2,c1,c2;
- // a1 = L1.a, b1 = L1.b, c1 = L1.c;
- // a2 = L2.a, b2 = L2.b, c2 = L2.c;
- // int d = a1 * b2 - a2 * b1;
- // if(d == 0)
- // return NoInterSection;
- // int dx = c1*b2-c2*b1;
- // int dy = a1*c2-a2*c1;
- // return pt(-1.0*dx/d,-1.0*dy/d);
- //}
- inline int area (pt a, pt b, pt c) {
- return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
- }
- inline bool intersect_1 (int a, int b, int c, int d) {
- if (a > b) swap (a, b);
- if (c > d) swap (c, d);
- return max(a,c) <= min(b,d);
- }
- bool intersect (pt a, pt b, pt c, pt d) {
- return intersect_1 (a.x, b.x, c.x, d.x)
- && intersect_1 (a.y, b.y, c.y, d.y)
- && area(a,b,c) * area(a,b,d) <= 0
- && area(c,d,a) * area(c,d,b) <= 0;
- }
- struct Monogon{
- vector<pt> dots;
- int n;
- Monogon(){}
- void Read(){
- int sz;
- cin >> sz;
- n = sz;
- dots.resize(sz);
- for(auto& p : dots){
- int x,y;
- cin >> x >> y;
- p.x = x;
- p.y = y;
- // cin >> p.x >> p.y;
- }
- dots.pb(dots[0]);
- }
- bool LiesIn(pt& p){
- pt p2 = pt(-(int)1e4-rnd()%111,-(int)1e4+(int)rnd()%1111);
- int c = 0;
- for(int i = 0; i + 1 < dots.size(); i++){
- pt p21 = dots[i], p22 = dots[i+1];
- c ^= intersect(p2,p,p21,p22);
- }
- return c == 1;
- }
- bool LiesIn(Monogon& b){
- // bool ok = 1;
- for(auto& p : b.dots){
- if(!LiesIn(p)){
- return false;
- }
- }
- return true;
- }
- bool HasIntersection(Monogon& b){
- for(auto& p : b.dots){
- if(LiesIn(p)){
- // cerr << p.x << " " << p.y << "\n";
- return true;
- }
- }
- return false;
- }
- };
- bool check(Monogon& a,Monogon& b){
- if(a.HasIntersection(b) || b.HasIntersection(a))
- return true;
- for(int i = 0; i + 1 < a.dots.size(); i++){
- pt p11 = a.dots[i], p12 = a.dots[i+1];
- for(int j = 0; j + 1 < b.dots.size(); j++){
- pt p21 = b.dots[j], p22 = b.dots[j+1];
- if(intersect(p11,p12,p21,p22)){
- return true;
- }
- }
- }
- return false;
- }
- void solve(){
- // cerr << HasIntersection(pt(6ll,-1ll),pt(6ll,4ll),pt(0ll,0ll),pt(10ll,0ll)) << "\n";
- // return;
- Monogon a,b;
- a.Read(), b.Read();
- cout << (check(a,b) ? "YES" : "NO") << "\n";
- // Line L(pt(6,10.46),pt(6.65,10.69));
- //
- // cout << fixed << setprecision(10) << L.a << " " << L.b << " " << L.c << "\n";
- return;
- }
- signed main(){
- ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
- int tests = 1;
- cin >> tests;
- for(int test = 1; test <= tests; test++){
- // cerr << "test = " << test << "\n";
- solve();
- }
- return 0;
- }
- /**
- (x-x1)/(x2-x1) = (y-y1)/(y2-y1)
- (x-x1)*(y2-y1) = (y-y1)*(x2-x1)
- x*(y2-y1) - x1*(y2-y1) = y*(x2-x1) - y1*(x2-x1)
- x*(y2-y1) + y*(x1-x2) - x1*y2 + x1*y1 = y1*x1 - y1*x2
- x*(y2-y1) + y*(x1-x2) - x1*y2 + y1*x2 = 0
- 1
- 3
- 0 -1
- 1 1
- -1 1
- 3
- 0 2
- -1 -2
- 1 -2
- 2.85 3.12
- 8.932
- 2.4669
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement