Submission #70478

#	Time	Username	Problem	Language	Result	Execution time	Memory
70478		spencercompton	The Forest of Fangorn (CEOI14_fangorn)	Java	50 / 100	3093 ms	64744 KiB

fangorn

import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
 
public class fangorn {
	public static double eps = 1e-9;
	public static class Obj implements Comparable<Obj>{
		public double dx, dy;
		public boolean g;
		Obj(double a, double b, boolean c){
			dx = a;
			dy = b;
			g = c;
		}
		public int compareTo(Obj o) {
			return Double.compare(Math.atan2(dy, dx), Math.atan2(o.dy, o.dx));
		}
	}
	public static int h, w;
	public static boolean sect(double sx1, double sy1, double ex1, double ey1, double sx2,
			double sy2, double ex2, double ey2) {
		if(Line2D.linesIntersect(sx1, sy1, ex1, ey1, sx2, sy2, ex2, ey2)) {
			return true;
		}
		if(Line2D.ptSegDist(sx1, sy1, ex1, ey1, ex2, ey2) < eps) {
			return true;
		}
		if(Line2D.ptSegDist(sx2, sy2, ex2, ey2, ex1, ey1) < eps) {
			return true;
		}
		if(Math.abs(sx1-sx2)<eps && Math.abs(sy1-sy2)<eps) {
			return true;
		}
		return Math.abs(ex1-ex2)<eps && Math.abs(ey1-ey2)<eps;
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		w = in.nextInt();
		h = in.nextInt();
		int gx = in.nextInt();
		int gy = in.nextInt();
		int c = in.nextInt();
		boolean[] ok = new boolean[c];
		Arrays.fill(ok, true);
		double[][] bases = new double[c][2];
		for(int i = 0; i<c; i++) {
			for(int j = 0; j<2; j++) {
				bases[i][j] = in.nextInt();
			}
		}
		int n = in.nextInt();
		double[][] trees = new double[n][2];
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<2; j++) {
				trees[i][j] = in.nextInt();
			}
		}
		ArrayList<Double> sy = new ArrayList<Double>();
		ArrayList<Double> sx = new ArrayList<Double>();
		ArrayList<Double> ey = new ArrayList<Double>();
		ArrayList<Double> ex = new ArrayList<Double>();
		for(int i = 0; i<n; i++) {
			ArrayList<Obj> li = new ArrayList<Obj>();
			for(int j = 0; j<n; j++) {
				if(i==j) {
					continue;
				}
				li.add(new Obj(trees[i][0]-trees[j][0],trees[i][1]-trees[j][1],false));
			}
			li.add(new Obj(gx-trees[i][0],gy-trees[i][1],true));
			Collections.sort(li);
			for(int j = 0; j<li.size(); j++) {
				if(!li.get(j).g) {
					continue;
				}
				int ind = (j+li.size()-1)%li.size();
				double dx = li.get(ind).dx;
				double dy = li.get(ind).dy;
				double len = Math.sqrt(dx*dx + dy*dy);
				dx /= len;
				dy /= len;
				double lo = 0.0;
				double hi = 1.0;
				while(true) {
					double nx = trees[i][0] + dx*hi;
					double ny = trees[i][1] + dy*hi;
					if(nx>=0 && nx<=w && ny>=0 && ny<=h) {
						hi *= 2.0;
					}
					else {
						break;
					}
				}
				int cnt = 0;
				while(hi>lo && cnt<500) {
					cnt++;
					double mid = (lo+hi)/2.0;
					double nx = trees[i][0] + dx*mid;
					double ny = trees[i][1] + dy*mid;
					if(nx>=0 && nx<=w && nx>=0 && ny<=h) {
						lo = mid;
					}
					else{
						hi = mid;
					}
				}
				sx.add(trees[i][0]);
				sy.add(trees[i][1]);
				ex.add(trees[i][0] + dx*lo);
				ey.add(trees[i][1] + dy*lo);
				
				
				ind = (j+1)%li.size();
				dx = li.get(ind).dx;
				dy = li.get(ind).dy;
				len = Math.sqrt(dx*dx + dy*dy);
				dx /= len;
				dy /= len;
				lo = 0.0;
				hi = 1.0;
				while(true) {
					double nx = trees[i][0] + dx*hi;
					double ny = trees[i][1] + dy*hi;
					if(nx>=0 && nx<=w && ny>=0 && ny<=h) {
						hi *= 2.0;
					}
					else {
						break;
					}
				}
				cnt = 0;
				while(hi>lo && cnt<500) {
					double mid = (lo+hi)/2.0;
					cnt++;
					double nx = trees[i][0] + dx*mid;
					double ny = trees[i][1] + dy*mid;
					if(nx>=0 && nx<=w && nx>=0 && ny<=h) {
						lo = mid;
					}
					else{
						hi = mid;
					}
				}
				sx.add(trees[i][0]);
				sy.add(trees[i][1]);
				ex.add(trees[i][0] + dx*lo);
				ey.add(trees[i][1] + dy*lo);
			}
		}
		for(int i = 0; i<sx.size(); i++) {
			for(int j = i+1; j<sx.size(); j++) {
				if(!sect(sx.get(i),sy.get(i),ex.get(i),ey.get(i),sx.get(j),sy.get(j),ex.get(j),ey.get(j))) {
					continue;
				}
				double lo = 0.0;
				double hi = 1.0;
				double dx = ex.get(j)-sx.get(j);
				double dy = ey.get(j)-sy.get(j);
				int cnt = 0;
				while(hi>lo && cnt<500) {
					cnt++;
					double mid = (lo+hi)/2.0;
					if(sect(sx.get(i),sy.get(i),ex.get(i),ey.get(i),sx.get(j),sy.get(j),sx.get(j)+dx*mid,sy.get(j)+dy*mid)) {
						hi = mid;
					}
					else {
						lo = mid;
					}
				}
				double px = sx.get(j)+dx*lo;
				double py = sy.get(j)+dy*lo;
				double a1 = Math.atan2(ey.get(i)-py, ex.get(i)-px);
				double a2 = Math.atan2(ey.get(j)-py, ex.get(j)-px);
				if(a1>a2) {
					double tmp = a1;
					a1 = a2;
					a2 = tmp;
				}
				double ag = Math.atan2(gy-py, gx-px);
				for(int k = 0; k<c; k++) {
					double acur = Math.atan2(bases[k][1]-py, bases[k][0]-px);
					if((acur>=a1 && acur<=a2) != (ag>=a1 && ag<=a2)) {
						ok[k] = false;
					}
				}
			}
		}
		ArrayList<Integer> ans = new ArrayList<Integer>();
		for(int i = 0; i<c; i++) {
			if(ok[i]) {
				ans.add(i+1);
			}
		}
		System.out.println(ans.size());
		if(ans.size()>0) {
			System.out.print(ans.get(0));
			for(int i = 1; i<ans.size(); i++) {
				System.out.print(" " +ans.get(i));
			}
			System.out.println();
		}
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20