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();
	}
}

Download