답안 #70499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70499 2018-08-23T04:49:25 Z spencercompton The Forest of Fangorn (CEOI14_fangorn) Java 11
50 / 100
3000 ms 64248 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 int its = 3;
	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<its) {
					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<its) {
					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<its) {
					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();
		}
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 11740 KB Output is correct
2 Correct 170 ms 11740 KB Output is correct
3 Correct 163 ms 11740 KB Output is correct
4 Correct 171 ms 12056 KB Output is correct
5 Correct 170 ms 12056 KB Output is correct
6 Correct 165 ms 12144 KB Output is correct
7 Correct 239 ms 12908 KB Output is correct
8 Correct 234 ms 12908 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 12908 KB Output is correct
2 Correct 234 ms 12908 KB Output is correct
3 Correct 233 ms 13268 KB Output is correct
4 Correct 246 ms 13300 KB Output is correct
5 Correct 232 ms 13300 KB Output is correct
6 Correct 334 ms 20068 KB Output is correct
7 Correct 175 ms 20068 KB Output is correct
8 Correct 172 ms 20068 KB Output is correct
9 Correct 221 ms 20068 KB Output is correct
10 Correct 536 ms 23860 KB Output is correct
11 Correct 596 ms 24784 KB Output is correct
12 Correct 594 ms 26824 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 26824 KB Output is correct
2 Correct 212 ms 26824 KB Output is correct
3 Correct 207 ms 26824 KB Output is correct
4 Execution timed out 3083 ms 64248 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3104 ms 64248 KB Time limit exceeded
2 Halted 0 ms 0 KB -