답안 #70436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70436 2018-08-22T22:21:33 Z spencercompton The Forest of Fangorn (CEOI14_fangorn) Java 11
10 / 100
3000 ms 27292 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-10;
	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;
					}
				}
				while(hi-lo>eps) {
					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;
					}
				}
				while(hi-lo>eps) {
					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);
			}
		}
		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);
				while(hi-lo>eps) {
					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();
		}
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 11476 KB Output is correct
2 Correct 160 ms 11580 KB Output is correct
3 Incorrect 156 ms 11692 KB Output isn't correct
4 Correct 171 ms 11900 KB Output is correct
5 Correct 169 ms 11964 KB Output is correct
6 Correct 155 ms 11964 KB Output is correct
7 Execution timed out 3056 ms 21048 KB Time limit exceeded
8 Execution timed out 3015 ms 21048 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 21048 KB Output is correct
2 Correct 182 ms 21048 KB Output is correct
3 Correct 229 ms 21048 KB Output is correct
4 Correct 273 ms 21048 KB Output is correct
5 Correct 274 ms 21048 KB Output is correct
6 Correct 337 ms 21048 KB Output is correct
7 Incorrect 140 ms 21048 KB Output isn't correct
8 Correct 175 ms 21048 KB Output is correct
9 Correct 221 ms 21048 KB Output is correct
10 Incorrect 824 ms 26404 KB Output isn't correct
11 Execution timed out 3044 ms 26404 KB Time limit exceeded
12 Execution timed out 3052 ms 26404 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 26404 KB Output is correct
2 Correct 196 ms 26404 KB Output is correct
3 Correct 202 ms 26404 KB Output is correct
4 Execution timed out 3008 ms 26404 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3088 ms 27292 KB Time limit exceeded
2 Halted 0 ms 0 KB -