| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 70432 | spencercompton | The Forest of Fangorn (CEOI14_fangorn) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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();
}
}