METERAIN - Mưa thiên thạch
Tác giả: khuc_tuan
Ngôn ngữ: Java
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 {
BufferedReader kb=new BufferedReader(new InputStreamReader(System.in));
int dx=0,dy=0,tx=0,ty=0;
boolean ok=false;
n=parseInt(kb.readLine());
dag = new Line[n];
for(int i=0;i<n;++i) {
StringTokenizer st=new StringTokenizer(kb.readLine());
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);
m=parseInt(kb.readLine());
ps=new PointI[m];
for(int i=0;i<m;++i) {
StringTokenizer st=new StringTokenizer(kb.readLine());
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;
}
});
LinkedList<Line> ts = new LinkedList<Line>();
for(Line q : dag) ts.add(q);
Collections.sort(ts, new Comparator<Line>(){
public int compare(Line a,Line b) {
return a.a.x-b.a.x;
}
});
LinkedList<Line> ds = new LinkedList<Line>();
LinkedList<Line> px = new LinkedList<Line>();
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) {
ds.add(x);
ts.removeFirst();
}
else break;
}
px.clear();
for(Line x : ds) if(x.b.x>=ps[i].x) px.add(x);
ds.clear();
for(Line x : px) ds.add(x);
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();
}
}