Submission #70441

# Submission time Handle Problem Language Result Execution time Memory
70441 2018-08-22T22:29:45 Z spencercompton The Forest of Fangorn (CEOI14_fangorn) Java 11
10 / 100
3000 ms 66384 KB
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(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);
		h = in.nextInt();
		w = 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(cnt<100) {
					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(cnt<100) {
					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(cnt<100) {
					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();
		}
	}
}
# Verdict Execution time Memory Grader output
1 Correct 161 ms 11752 KB Output is correct
2 Correct 167 ms 11768 KB Output is correct
3 Incorrect 160 ms 11768 KB Output isn't correct
4 Correct 162 ms 12076 KB Output is correct
5 Correct 149 ms 12076 KB Output is correct
6 Correct 145 ms 12212 KB Output is correct
7 Correct 251 ms 18796 KB Output is correct
8 Incorrect 409 ms 20336 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 202 ms 20336 KB Output is correct
2 Correct 211 ms 20336 KB Output is correct
3 Correct 330 ms 20336 KB Output is correct
4 Correct 346 ms 20336 KB Output is correct
5 Correct 306 ms 20336 KB Output is correct
6 Correct 485 ms 22984 KB Output is correct
7 Incorrect 155 ms 22984 KB Output isn't correct
8 Correct 193 ms 22984 KB Output is correct
9 Correct 316 ms 22984 KB Output is correct
10 Incorrect 864 ms 26132 KB Output isn't correct
11 Correct 889 ms 26132 KB Output is correct
12 Incorrect 929 ms 28212 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 190 ms 28212 KB Output is correct
2 Correct 218 ms 28212 KB Output is correct
3 Correct 204 ms 28212 KB Output is correct
4 Execution timed out 3035 ms 63424 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 3020 ms 66384 KB Time limit exceeded
2 Halted 0 ms 0 KB -