Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment