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(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();
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
11256 KB |
Output is correct |
| 2 |
Correct |
162 ms |
11816 KB |
Output is correct |
| 3 |
Correct |
175 ms |
11816 KB |
Output is correct |
| 4 |
Correct |
173 ms |
11816 KB |
Output is correct |
| 5 |
Correct |
168 ms |
11968 KB |
Output is correct |
| 6 |
Correct |
171 ms |
11968 KB |
Output is correct |
| 7 |
Correct |
257 ms |
12524 KB |
Output is correct |
| 8 |
Correct |
276 ms |
12832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
175 ms |
12832 KB |
Output is correct |
| 2 |
Correct |
201 ms |
12832 KB |
Output is correct |
| 3 |
Correct |
225 ms |
12980 KB |
Output is correct |
| 4 |
Correct |
253 ms |
12980 KB |
Output is correct |
| 5 |
Correct |
253 ms |
13164 KB |
Output is correct |
| 6 |
Correct |
354 ms |
20104 KB |
Output is correct |
| 7 |
Correct |
183 ms |
20104 KB |
Output is correct |
| 8 |
Correct |
178 ms |
20104 KB |
Output is correct |
| 9 |
Correct |
256 ms |
20104 KB |
Output is correct |
| 10 |
Correct |
584 ms |
22768 KB |
Output is correct |
| 11 |
Correct |
652 ms |
24948 KB |
Output is correct |
| 12 |
Correct |
581 ms |
25380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
25380 KB |
Output is correct |
| 2 |
Correct |
174 ms |
25380 KB |
Output is correct |
| 3 |
Correct |
173 ms |
25380 KB |
Output is correct |
| 4 |
Execution timed out |
3055 ms |
64036 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3105 ms |
64980 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
