## Editorial for Mưa thiên thạch

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#include <bits/stdc++.h>
#define X first
#define Y second
#define long long long
const int N = 5050;
using namespace std;
typedef pair<int, int> ii;
void operator -= (ii& A, ii B) {A.X -= B.X; A.Y -= B.Y;}
bool CCW(ii &A, ii B, ii C) {C -= B; B -= A; return (long)B.X * C.Y >= (long)B.Y * C.X;}
int n, m;
ii a[N];

int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d %d", &a[i].X, &a[i].Y);
scanf("%d", &m);
ii b;
while (m--) {
scanf("%d %d", &b.X, &b.Y);
bool inside = true; a[0] = a[n];
for(int i = 1; i <= n; i++)
if (CCW(a[i], a[i - 1], b)) {
inside = false; break;
}
if (inside) printf("YES\n");
else printf("NO\n");
}
return 0;
}


#### Code mẫu của RR

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

const double EPS = 1e-6;

inline int cmp(double a, double b) {
return (a < b - EPS) ? -1 : ((a > b + EPS) ? 1 : 0);
}

struct Point {
double x, y;
Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}

Point operator + (Point a) { return Point(x+a.x, y+a.y); }
Point operator - (Point a) { return Point(x-a.x, y-a.y); }
Point operator * (double k) { return Point(x*k, y*k); }
Point operator / (double k) { return Point(x/k, y/k); }

double operator * (Point a) { return x*a.x + y*a.y; } // dot product
double operator % (Point a) { return x*a.y - y*a.x; } // cross product

int cmp(Point q) const { if (int t = ::cmp(x,q.x)) return t; return ::cmp(y,q.y); }

#define Comp(x) bool operator x (Point q) const { return cmp(q) x 0; }
Comp(>) Comp(<) Comp(==) Comp(>=) Comp(<=) Comp(!=)
#undef Comp

Point conj() { return Point(x, -y); }
double norm() { return x*x + y*y; }

// Note: There are 2 ways for implementing len():
// 1. sqrt(norm()) --> fast, but inaccurate (produce some values that are of order X^2)
// 2. hypot(x, y) --> slow, but much more accurate
double len() { return sqrt(norm()); }

Point rotate(double alpha) {
double cosa = cos(alpha), sina = sin(alpha);
return Point(x * cosa - y * sina, x * sina + y * cosa);
}
};

typedef vector<Point> Polygon;

inline int iabs(int x) { if (x < 0) return -x; else return x; }

#define Det(a,b,c) ((double)(b.x-a.x)*(double)(c.y-a.y)-(double)(b.y-a.y)*(c.x-a.x))
bool in_convex(vector<Point>& l, Point p){
int a = 1, b = l.size()-1, c;
if (Det(l[0], l[a], l[b]) > 0) swap(a,b);
if (Det(l[0], l[a], p) >= 0 || Det(l[0], l[b], p) <= 0) return false;
while(iabs(a-b) > 1) {
c = (a+b)/2;
if (Det(l[0], l[c], p) > 0) b = c; else a = c;
}
return Det(l[a], l[b], p) < 0;
}

int main() {
ios :: sync_with_stdio(false); cin.tie(NULL);
int n;
while (cin >> n) {
Polygon a;
for(int i = 0; i < n; ++i) {
int x, y; cin >> x >> y;
a.push_back(Point(x, y));
}
int m; cin >> m;
for(int i = 0; i < m; ++i) {
int x, y; cin >> x >> y;
Point P(x, y);

if (in_convex(a, P)) cout << "YES";
else cout << "NO";
cout << "\n";
}
}
}


#### Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define oo 1111111111
#define nmax 100111
#define MAX 222

using namespace std;

struct point{
int x,y;
bool operator == (point D) const{
return (x == D.x && y == D.y);
}
};

point  a[nmax],p;
int n,m;

long long kc(point a,point b){
long long X = (b.x-a.x);
long long Y = (b.y-a.y);
return X*X+Y*Y;
}

bool behon(point a,point b,point bn){
long long ax,ay,bx,by;
ax = a.x - bn.x;
ay = a.y - bn.y;
bx = b.x - bn.x;
by = b.y - bn.y;
if(ay!=0 && by==0) return true;
if(ay==0||by==0) return false;
return ax*by>ay*bx;
}

void Sort(point a[],int l,int r){
int i = l,j = r;
point mid = a[(l+r)/2];
while(i<j){
while(behon(a[i],mid,a[0])) i++;
while(behon(mid,a[j],a[0])) j--;
if(i<=j) swap(a[i++],a[j--]);
}
if(i<r) Sort(a,i,r);
if(l<j) Sort(a,l,j);
}

int ccw(point p1,point p2,point p3){
long long a1,a2,b1,b2,t;
a1 = p2.x-p1.x;
a2 = p3.x-p1.x;
b1 = p2.y-p1.y;
b2 = p3.y-p1.y;
t = a1*b2-a2*b1;
if(t==0) return 0;
if(t>0) return 1;
return -1;
}

int graham(point a[],int n){
int m = 1;
for(int i = 2;i<=n;i++)
if(a[m].y>a[i].y) m = i;
for(int i = 1;i<=n;i++)
if(a[i].y==a[m].y && a[i].x>a[m].x)
m = i;
swap(a[1],a[m]);
a[0].x = a[1].x;
a[0].y = a[1].y-1;
Sort(a,2,n);
a[++n] = a[1];
m = 2;
bool ok = true;
for(int i = 3;i<=n;i++){
ok = true;
while(ccw(a[m],a[m-1],a[i])>=0){
if(ccw(a[m],a[m-1],a[1])==0){
ok = false;
if(kc(a[m],a[m-1])<kc(a[m-1],a[i]))
swap(a[m],a[i]);
break;
}
else m--;
}
if(ok) swap(a[++m],a[i]);
}
return --m;
}

long long stg(point a,point b,point c){
long long s = (b.x-a.x)*1LL*(b.y+a.y)+(c.x-b.x)*1LL*(c.y+b.y)+ (a.x-c.x)*1LL*(a.y+c.y);
return s>0?s:-s;
}

int namtrong(point p,int l,int r,point b[]){
while(r-l>2){
int mid = (l+r+1)/2;
int k = ccw(b[1],b[mid],p);
if(k==0){
if((b[1].x-p.x)*(b[mid].x-p.x)<0) return 1;;
return 0;
}
if(k==1) l = mid-1;
if(k==-1) r = mid;
}
point x,y,z;
x = b[1];
y = b[r];
z = b[r-1];
long long k = stg(x,y,z);
long long t = stg(x,y,p)+stg(x,z,p)+stg(y,z,p);
if(t>k) return 0;
int kk = ccw(x,y,p)*ccw(x,z,p)*ccw(y,z,p);
if(kk!=0) return 1;
if(p==x||p==y||p==z) return 0;
if(r==3){
if(n<=3) return 0;
if(ccw(x,y,p)==0)
return 1;
}
if(r==n &&ccw(x,z,p)==0)
return 1;
if(ccw(x,y,p)==0 && r!=n)
return 1;
if(ccw(x,z,p)==0 && r!=3)
return 1;
return 0;
}

int main(){
//freopen("METERAIN.in","r",stdin);
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d %d",&a[i].x,&a[i].y);
}
// printf("?\n");
n = graham(a,n);
//printf("?\n");
scanf("%d",&m);
for(int i = 1;i<=m;i++){
scanf("%d %d",&p.x,&p.y);
if(namtrong(p,1,n,a)) printf("YES\n");
else printf("NO\n");
}
// getch();
}


#### Code mẫu của skyvn97

#include<cstdio>
#define MAX   5050
typedef long long ll;
struct point {
ll x,y;
point(){}
point(const ll &_x,const ll &_y) {
x=_x;y=_y;
}
void inp(void) {
scanf("%lld",&x);
scanf("%lld",&y);
}
};
point a[MAX];
point ptl,ptr,pbl,pbr;
int n,m,tl,tr,bl,br;
void init(void) {
scanf("%d",&n);
int i;
for (i=0;i<n;i=i+1) a[i].inp();
ptl=a[0];ptr=a[0];pbl=a[0];pbr=a[0];
tl=0;tr=0;bl=0;br=0;
for (i=1;i<n;i=i+1) {
if (ptl.x>a[i].x || (ptl.x==a[i].x && ptl.y<a[i].y)) {
ptl=a[i];
tl=i;
}
if (pbl.x>a[i].x || (pbl.x==a[i].x && pbl.y>a[i].y)) {
pbl=a[i];
bl=i;
}
if (ptr.x<a[i].x || (ptr.x==a[i].x && ptr.y<a[i].y)) {
ptr=a[i];
tr=i;
}
if (pbr.x<a[i].x || (pbr.x==a[i].x && pbr.y>a[i].y)) {
pbr=a[i];
br=i;
}
}
}
int cmp(const point &a,const point &b,const point &c) {
if (a.x>b.x) return (cmp(b,a,c));
ll left=b.x*a.y-a.x*b.y+c.x*b.y-c.x*a.y;
ll right=c.y*b.x-c.y*a.x;
if (left>right) return (1);
if (left<right) return (-1);
return (0);
}
int find_bot(const ll &x0) {
int l,m,r;
l=(bl+1)%n;
r=br;
while (true) {
if (l==r) return (r);
if  ((l+1)%n==r) {
if (a[l].x>=x0) return (l);
return (r);
}
if (r>l) m=((l+r)/2)%n;
else m=((l+r+n)/2)%n;
if (a[m].x>=x0) r=m;
else l=(m+1)%n;
}
}
int find_top(const ll &x0) {
int l,m,r;
l=tl;
r=(tr+1)%n;
while (true) {
if (l==r) return (l);
if (l==(r+1)%n) {
if (a[r].x<=x0) return (r);
return (l);
}
if (l>r) m=((l+r)/2)%n;
else m=((l+r+n)/2)%n;
if (a[m].x<=x0) l=m;
else r=(m+1)%n;
}
}
bool check(const point &t) {
if (t.x<=pbl.x) return (false);
if (t.x>=pbr.x) return (false);
int ib=find_bot(t.x);
int it=find_top(t.x);
if (cmp(a[ib],a[(ib-1+n)%n],t)>=0) return (false);
if (cmp(a[it],a[(it-1+n)%n],t)<=0) return (false);
return (true);
}
void process(void) {
point t;
int i;
scanf("%d",&m);
for (i=1;i<=m;i=i+1) {
t.inp();
if (check(t)) printf("YES\n");
else printf("NO\n");
}
}
int main(void) {
init();
process();
return 0;
}


#### Code mẫu của khuc_tuan

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;
public class Main {
class Point {
public int x,y;
public Point(int _x,int _y) {
x=_x; y=_y;
}
}
class Line {
public Point a,b;
public Line(int x,int y,int u,int v) {
if(x<u) {
a = new Point(x,y);
b = new Point(u,v);
}
else {
b = new Point(x,y);
a = new Point(u,v);
}
}
}
class PointI {
public int x,y,i;
public PointI(int _x,int _y,int _i) {
x=_x; y=_y; i=_i;
}
}
int n,m;
Line[] dag;
PointI[] ps;
int[] result;
void nhap() throws Exception {
int dx=0,dy=0,tx=0,ty=0;
boolean ok=false;
dag = new Line[n];
for(int i=0;i<n;++i) {
int x=parseInt(st.nextToken()), y=parseInt(st.nextToken());
if(!ok) { dx=x; dy=y; ok=true; }
else dag[i-1] = new Line(tx,ty,x,y);
tx=x; ty=y;
}
dag[n-1] = new Line(dx,dy,tx,ty);
ps=new PointI[m];
for(int i=0;i<m;++i) {
int x=parseInt(st.nextToken()), y=parseInt(st.nextToken());
ps[i]=new PointI(x,y,i);
}
}
void xuly() {
Arrays.sort(ps,new Comparator<PointI>() {
public int compare(PointI a, PointI b) {
return a.x-b.x;
}
});
Collections.sort(ts, new Comparator<Line>(){
public int compare(Line a,Line b) {
return a.a.x-b.a.x;
}
});
result = new int[m];
for(int i=0;i<m;++i) {
while(ts.size()!=0) {
Line x = ts.getFirst();
if(x.a.x<=ps[i].x) {
ts.removeFirst();
}
else break;
}
px.clear();
for(Line x : ds) if(x.b.x>=ps[i].x) px.add(x);
ds.clear();
int res=0;
for(Line q : ds) {
if(((long)ps[i].y-q.a.y)*(q.b.x-q.a.x)==((long)ps[i].x-q.a.x)*(q.b.y-q.a.y))
if(ps[i].x>=q.a.x && ps[i].x<=q.b.x && ps[i].y>=Math.min(q.a.y,q.b.y) && ps[i].y<=Math.max(q.a.y,q.b.y)) {
res=0; break;
}
if(q.a.x!=q.b.x) {
if(q.a.x==ps[i].x && q.a.y>=ps[i].y) ++res;
else if(q.b.x>ps[i].x) {
double y = ((double)q.b.y-q.a.y)/(q.b.x-q.a.x)*(ps[i].x-q.a.x) + q.a.y;
if(y+1e-8 >= ps[i].y) ++res;
}
}
}
result[ps[i].i] = res%2;
}
for(int i=0;i<m;++i) System.out.println((result[i]==1)?"YES":"NO");
}
void run() throws Exception {
nhap();
xuly();
}
public static void main(String[] Args) throws Exception {
new Main().run();
}
}