Submission #70432

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
70432	2018-08-22T22:14:58 Z	spencercompton	The Forest of Fangorn (CEOI14_fangorn)	Java 11	Compilation error	0 ms	0 KB

fangorn

import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

	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)<1e-7 && Math.abs(sy1-sy2)<1e-7) {
			return true;
		}
		return Math.abs(ex1-ex2)<1e-7 && Math.abs(ey1-ey2)<1e-7;
	}
	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>1e-8) {
					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>1e-8) {
					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>1e-9) {
					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();
		}
	}

Compilation message

fangorn.java:19: error: class, interface, or enum expected
	public static int h, w;
	              ^
fangorn.java:20: error: class, interface, or enum expected
	public static boolean sect(double sx1, double sy1, double ex1, double ey1, double sx2,
	              ^
fangorn.java:24: error: class, interface, or enum expected
		}
		^
fangorn.java:27: error: class, interface, or enum expected
		}
		^
fangorn.java:29: error: class, interface, or enum expected
	}
	^
fangorn.java:30: error: class, interface, or enum expected
	public static void main(String[] args) {
	              ^
fangorn.java:32: error: class, interface, or enum expected
		h = in.nextInt();
		^
fangorn.java:33: error: class, interface, or enum expected
		w = in.nextInt();
		^
fangorn.java:34: error: class, interface, or enum expected
		int gx = in.nextInt();
		^
fangorn.java:35: error: class, interface, or enum expected
		int gy = in.nextInt();
		^
fangorn.java:36: error: class, interface, or enum expected
		int c = in.nextInt();
		^
fangorn.java:37: error: class, interface, or enum expected
		boolean[] ok = new boolean[c];
		^
fangorn.java:38: error: class, interface, or enum expected
		Arrays.fill(ok, true);
		^
fangorn.java:39: error: class, interface, or enum expected
		double[][] bases = new double[c][2];
		^
fangorn.java:40: error: class, interface, or enum expected
		for(int i = 0; i<c; i++) {
		^
fangorn.java:40: error: class, interface, or enum expected
		for(int i = 0; i<c; i++) {
		               ^
fangorn.java:40: error: class, interface, or enum expected
		for(int i = 0; i<c; i++) {
		                    ^
fangorn.java:41: error: class, interface, or enum expected
			for(int j = 0; j<2; j++) {
			               ^
fangorn.java:41: error: class, interface, or enum expected
			for(int j = 0; j<2; j++) {
			                    ^
fangorn.java:43: error: class, interface, or enum expected
			}
			^
fangorn.java:46: error: class, interface, or enum expected
		double[][] trees = new double[n][2];
		^
fangorn.java:47: error: class, interface, or enum expected
		for(int i = 0; i<n; i++) {
		^
fangorn.java:47: error: class, interface, or enum expected
		for(int i = 0; i<n; i++) {
		               ^
fangorn.java:47: error: class, interface, or enum expected
		for(int i = 0; i<n; i++) {
		                    ^
fangorn.java:48: error: class, interface, or enum expected
			for(int j = 0; j<2; j++) {
			               ^
fangorn.java:48: error: class, interface, or enum expected
			for(int j = 0; j<2; j++) {
			                    ^
fangorn.java:50: error: class, interface, or enum expected
			}
			^
fangorn.java:53: error: class, interface, or enum expected
		ArrayList<Double> sx = new ArrayList<Double>();
		^
fangorn.java:54: error: class, interface, or enum expected
		ArrayList<Double> ey = new ArrayList<Double>();
		^
fangorn.java:55: error: class, interface, or enum expected
		ArrayList<Double> ex = new ArrayList<Double>();
		^
fangorn.java:56: error: class, interface, or enum expected
		for(int i = 0; i<n; i++) {
		^
fangorn.java:56: error: class, interface, or enum expected
		for(int i = 0; i<n; i++) {
		               ^
fangorn.java:56: error: class, interface, or enum expected
		for(int i = 0; i<n; i++) {
		                    ^
fangorn.java:58: error: class, interface, or enum expected
			for(int j = 0; j<n; j++) {
			^
fangorn.java:58: error: class, interface, or enum expected
			for(int j = 0; j<n; j++) {
			               ^
fangorn.java:58: error: class, interface, or enum expected
			for(int j = 0; j<n; j++) {
			                    ^
fangorn.java:61: error: class, interface, or enum expected
				}
				^
fangorn.java:63: error: class, interface, or enum expected
			}
			^
fangorn.java:65: error: class, interface, or enum expected
			Collections.sort(li);
			^
fangorn.java:66: error: class, interface, or enum expected
			for(int j = 0; j<li.size(); j++) {
			^
fangorn.java:66: error: class, interface, or enum expected
			for(int j = 0; j<li.size(); j++) {
			               ^
fangorn.java:66: error: class, interface, or enum expected
			for(int j = 0; j<li.size(); j++) {
			                            ^
fangorn.java:69: error: class, interface, or enum expected
				}
				^
fangorn.java:71: error: class, interface, or enum expected
				double dx = li.get(ind).dx;
				^
fangorn.java:72: error: class, interface, or enum expected
				double dy = li.get(ind).dy;
				^
fangorn.java:73: error: class, interface, or enum expected
				double len = Math.sqrt(dx*dx + dy*dy);
				^
fangorn.java:74: error: class, interface, or enum expected
				dx /= len;
				^
fangorn.java:75: error: class, interface, or enum expected
				dy /= len;
				^
fangorn.java:76: error: class, interface, or enum expected
				double lo = 0.0;
				^
fangorn.java:77: error: class, interface, or enum expected
				double hi = 1.0;
				^
fangorn.java:78: error: class, interface, or enum expected
				while(true) {
				^
fangorn.java:80: error: class, interface, or enum expected
					double ny = trees[i][1] + dy*hi;
					^
fangorn.java:81: error: class, interface, or enum expected
					if(nx>=0 && nx<=w && ny>=0 && ny<=h) {
					^
fangorn.java:83: error: class, interface, or enum expected
					}
					^
fangorn.java:86: error: class, interface, or enum expected
					}
					^
fangorn.java:90: error: class, interface, or enum expected
					double nx = trees[i][0] + dx*mid;
					^
fangorn.java:91: error: class, interface, or enum expected
					double ny = trees[i][1] + dy*mid;
					^
fangorn.java:92: error: class, interface, or enum expected
					if(nx>=0 && nx<=w && nx>=0 && ny<=h) {
					^
fangorn.java:94: error: class, interface, or enum expected
					}
					^
fangorn.java:97: error: class, interface, or enum expected
					}
					^
fangorn.java:100: error: class, interface, or enum expected
				sy.add(trees[i][1]);
				^
fangorn.java:101: error: class, interface, or enum expected
				ex.add(trees[i][0] + dx*lo);
				^
fangorn.java:102: error: class, interface, or enum expected
				ey.add(trees[i][1] + dy*lo);
				^
fangorn.java:105: error: class, interface, or enum expected
				ind = (j+1)%li.size();
				^
fangorn.java:106: error: class, interface, or enum expected
				dx = li.get(ind).dx;
				^
fangorn.java:107: error: class, interface, or enum expected
				dy = li.get(ind).dy;
				^
fangorn.java:108: error: class, interface, or enum expected
				len = Math.sqrt(dx*dx + dy*dy);
				^
fangorn.java:109: error: class, interface, or enum expected
				dx /= len;
				^
fangorn.java:110: error: class, interface, or enum expected
				dy /= len;
				^
fangorn.java:111: error: class, interface, or enum expected
				lo = 0.0;
				^
fangorn.java:112: error: class, interface, or enum expected
				hi = 1.0;
				^
fangorn.java:113: error: class, interface, or enum expected
				while(true) {
				^
fangorn.java:115: error: class, interface, or enum expected
					double ny = trees[i][1] + dy*hi;
					^
fangorn.java:116: error: class, interface, or enum expected
					if(nx>=0 && nx<=w && ny>=0 && ny<=h) {
					^
fangorn.java:118: error: class, interface, or enum expected
					}
					^
fangorn.java:121: error: class, interface, or enum expected
					}
					^
fangorn.java:125: error: class, interface, or enum expected
					double nx = trees[i][0] + dx*mid;
					^
fangorn.java:126: error: class, interface, or enum expected
					double ny = trees[i][1] + dy*mid;
					^
fangorn.java:127: error: class, interface, or enum expected
					if(nx>=0 && nx<=w && nx>=0 && ny<=h) {
					^
fangorn.java:129: error: class, interface, or enum expected
					}
					^
fangorn.java:132: error: class, interface, or enum expected
					}
					^
fangorn.java:135: error: class, interface, or enum expected
				sy.add(trees[i][1]);
				^
fangorn.java:136: error: class, interface, or enum expected
				ex.add(trees[i][0] + dx*lo);
				^
fangorn.java:137: error: class, interface, or enum expected
				ey.add(trees[i][1] + dy*lo);
				^
fangorn.java:138: error: class, interface, or enum expected
			}
			^
fangorn.java:140: error: class, interface, or enum expected
		for(int i = 0; i<sx.size(); i++) {
		               ^
fangorn.java:140: error: class, interface, or enum expected
		for(int i = 0; i<sx.size(); i++) {
		                            ^
fangorn.java:141: error: class, interface, or enum expected
			for(int j = i+1; j<sx.size(); j++) {
			                 ^
fangorn.java:141: error: class, interface, or enum expected
			for(int j = i+1; j<sx.size(); j++) {
			                              ^
fangorn.java:144: error: class, interface, or enum expected
				}
				^
fangorn.java:146: error: class, interface, or enum expected
				double hi = 1.0;
				^
fangorn.java:147: error: class, interface, or enum expected
				double dx = ex.get(j)-sx.get(j);
				^
fangorn.java:148: error: class, interface, or enum expected
				double dy = ey.get(j)-sy.get(j);
				^
fangorn.java:149: error: class, interface, or enum expected
				while(hi-lo>1e-9) {
				^
fangorn.java:151: error: class, interface, or enum expected
					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)) {
					^
fangorn.java:153: error: class, interface, or enum expected
					}
					^
fangorn.java:156: error: class, interface, or enum expected
					}
					^
fangorn.java:159: error: class, interface, or enum expected
				double py = sy.get(j)+dy*lo;
				^
fangorn.java:160: error: class, interface, or enum expected
				double a1 = Math.atan2(ey.get(i)-py, ex.get(i)-px);
				^
fangorn.java:161: error: class, interface, or enum expected
				double a2 = Math.atan2(ey.get(j)-py, ex.get(j)-px);
				^
100 errors