pointinpolygon.cpp

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 10;
struct Pt {
	ll x, y;
	Pt(ll _x = 0, ll _y = 0) : x(_x), y(_y) {}
	Pt operator+(const Pt& o) { return Pt(x+o.x, y+o.y); } // soma de vetores
	Pt operator-(const Pt& o) { return Pt(x-o.x, y-o.y); } // subtração de vetores
	Pt operator*(ll b) 	  { return Pt(x*b, y*b); } //retorna o vetor escalado por b 
	void operator+=(const Pt& o) { x += o.x, y += o.y; } // somar vetores com o operador +=
	void operator-=(const Pt& o) { x -= o.x, y -= o.y; } // subtrair vetores com o operador -=
	void operator*=(ll b) 	{ x*=b, y*=b; } //retorna o vetor escalado por b 
	ll dot(const Pt& o) { return x*o.x + y*o.y; } // dot - produto escalar
	ll cross(const Pt& o) { return x*o.y - y*o.x; } // cross - produto vetorial
	bool operator<(Pt v1) const{ // usado na comparação para o voncexhull
		if(x == v1.x) return y < v1.y;
		return x < v1.x; 
	}
} pointsA[112345];

std::vector<Pt> upper, lower;
int n, m;

Pt l, f;
ll minx, miny, maxx, maxy;
void convexhull(){ // faz o upper e o lower hull do polígono convexo dado,
				   // e encontra os pontos extremos;
	int it1 = 0, it2 = 0;
	for(int i = 0; i < n; i++){
		minx = min(pointsA[i].x, minx), miny = min(pointsA[i].y, miny);
		maxx = max(pointsA[i].x, maxx), maxy = max(pointsA[i].y, maxy);

		while(it1 >= 2 && (pointsA[i] - upper[it1 - 2]).cross(upper[it1 - 1] - upper[it1  - 2]) < 0){
			upper.pop_back();
			it1--;
		}
		upper.push_back(pointsA[i]);
		it1++;
		while(it2 >= 2 && (pointsA[i] - lower[it2 - 2]).cross(lower[it2 - 1] - lower[it2  - 2]) > 0){
			lower.pop_back();
			it2--;
		}
		lower.push_back(pointsA[i]);
		it2++;
	}
	l = upper[0], f = upper[it1 - 1];
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%lld %lld", &pointsA[i].x, &pointsA[i].y);
	}
	sort(pointsA, pointsA + n);
	convexhull();
	scanf("%d", &m);

	for(int i = 0; i < m; i++){
		Pt qi;
		scanf("%lld %lld", &qi.x, &qi.y);
		if(qi.x >= maxx || qi.x <= minx || qi.y >= maxy || qi.y <= miny){
			printf("NO\n"); //existe ao menos um ponto fora do poligono convexo, ja que ele não está no retangulo
			return 0;
		}
		if((f - l).cross(qi - f) > 0){
			int q = upper_bound(upper.begin(), upper.end(), qi) - upper.begin(); //primeiro ponto a direita do verificado no upper hull
			if(q == upper.size()) q--;
			int p = q -1;
			Pt a = upper[q], b = upper[p];
			if((a - b).cross(qi - b) >= 0){
				//esse ponto está fora do upper hull, e acima da linha, logo esta fora do poligono
				printf("NO\n");
				return 0;
			}
		}else{
			int q = upper_bound(lower.begin(), lower.end(), qi) - lower.begin(); //primeiro ponto a direita do verificado no uplower hull 
			if(q == lower.size()) q--;
			int p = q -1;
			Pt a = lower[q], b = lower[p];
			if((a - b).cross(qi - b) <= 0){
				//esse ponto está fora do lower hull, e abaixo da linha, logo esta fora do poligono
				printf("NO\n");
				return 0;
			}
			
			
		}

	}
	printf("YES\n");
	

}