-
Notifications
You must be signed in to change notification settings - Fork 0
/
cookie.java
212 lines (185 loc) · 6.43 KB
/
cookie.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
/* problema cookie
las observaciones claves son las siguientes:
1) Todos los polígonos que se forman dentro de la galleta son convexos.
2) cada polígono que es "atravesado" por un cut puede a lo sumo dividirse en otros dos polígonos convexos(debido a que el polígono original es convexo).
Entonces el algoritmo consiste en mantener los polígonos que se forman en la galleta hasta el cut i-ésimo, para tener los polígonos después del cut (i+1) entonces se cogen cada uno de los polígonos después del cut (i) y se mira si se intersectan con la linea que representa el cut (i+1) , si no se intersectan entonces el polígono continua así (completo), si se intersectan entonces ese polígono se divide en dos nuevos polígonos. Para hallar los dos polígonos resultantes se usó una ligera modificación del algorimto de Sutherland–Hodgman[1] (el cual me pareció muy elegante e intuitivo). Es importante aclarar que al inicio el único polígono es la galleta.
Finalmente , después de procesar todos los cut's entonces se tienen todos los polígonos formados y ya se pueden usar los algoritmos de la ancheta para saber si un punto (galleta) está dentro de un polígono y para calcular el área del mismo.
En cuanto a complejidad, la construcción de los polígonos es aproximadamente O(n^2) (sin tener en cuenta que la "intersección" de la recta con un polígono implica recorrer las aristas de este), donde n representa la cantidad de polígonos que se forman al final. Y la parte de mirar si las galletas están dentro de cada polígono es aproximadamente O(n*c), donde c representa la cantidad de galletas.
Si no estoy equivocado en el peor de los casos n está entre 600 y 700, en todo caso la solución corrió en 1.4 segundos.
[1]http://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm
Nos hablamos y si tienen alguna inquietud no duden en compartirla*/
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class cookie {
static class point{
double x,y;
public point(double xx,double yy){
x=xx;
y=yy;
}
public point sub(point a){
return new point(x - a.x,y - a.y);
}
public point add(point a){
return new point(x + a.x,y + a.y);
}
public double cross(point a){
return x*a.y - y*a.x;
}
public point multbyscalar(double ua) {
return new point(ua*x,ua*y);
}
}
static point intersectionbtwlines(point p1,point p2,point p3,point p4){
point p2_p1=p2.sub(p1);
point p4_p3=p4.sub(p3);
double den=p2_p1.cross(p4_p3);
if (Math.abs(den)<eps)//the lines are parallel or coincident
return null;
point p1_p3=p1.sub(p3);
double num=p4_p3.cross(p1_p3);
double ua=num/den;
return p2_p1.multbyscalar(ua).add(p1);
}
static double eps=1e-7;
static point[] sutherland_hodgman(point[] line,point[] poly,int flag){
ArrayList<point> output=new ArrayList<point>();
point S=poly[poly.length-1];
for(int i=0;i<poly.length;i++){
point E=poly[i];
double ecross=line[1].sub(line[0]).cross(E.sub(line[0]));
double scross=line[1].sub(line[0]).cross(S.sub(line[0]));
if (Math.abs(ecross)<eps)
output.add(E);
else if (ecross*flag>eps){
if (scross*flag<-eps)
output.add(intersectionbtwlines(line[0],line[1],S,E));
output.add(E);
}
else if(scross*flag>eps)
output.add(intersectionbtwlines(line[0],line[1],S,E));
S=E;
}
point[] ret=new point[output.size()];
return output.toArray(ret);
}
static point[][] bisection(point[] line, point[] poly){
point[] uno=sutherland_hodgman(line,poly,1);
point[] dos=sutherland_hodgman(line,poly,-1);
int amount=(uno.length>2)?1:0;
amount+=(dos.length>2)?1:0;
point[][] ret=new point[amount][];
int index=0;
if (uno.length>2)
ret[index++]=uno;
if (dos.length>2)
ret[index++]=dos;
return ret;
}
static class Scanner{
BufferedReader br=null;
StringTokenizer tk=null;
public Scanner() throws FileNotFoundException{
br = new BufferedReader(new FileReader("cookie.in"));
}
public String next() throws IOException{
while(tk==null || !tk.hasMoreTokens())
tk=new StringTokenizer(br.readLine());
return tk.nextToken();
}
public int nextInt() throws NumberFormatException, IOException{
return Integer.valueOf(next());
}
public double nextDouble() throws NumberFormatException, IOException {
return Double.valueOf(next());
}
}
static int L,S,K;
static point[] initpoly(int L){
point[] ret=new point[4];
ret[0]=new point(0,0);
ret[1]=new point(L,0);
ret[2]=new point(L,L);
ret[3]=new point(0,L);
return ret;
}
static double polygonarea(point[] a, int n){
double r=0;
for(int i=0;i<n;i++)
r+=a[i].cross(a[(i+1)%n]);
return Math.abs(r/2.0);
}
static double ccw(point a,point b,point c){
return a.sub(b).cross(c.sub(b));
}
static boolean insidepolygon(point[] p , int n,point t){
int mask=0;
for(int i=0;i<n;i++){
double z=ccw(p[i],p[(i+1)%n],t);
if (Math.abs(z)<eps)
return false;
else if (z<0)
mask |= 1;
else if (z>0)
mask |= 2;
if (mask==3)
return false;
}
return true;
}
static void dbg(point[] a){
System.out.println("===");
for(int i=0;i<a.length;i++)
System.out.println(a[i].x+" "+a[i].y);
System.out.println("===");
}
static point[] chips=new point[5010];
public static void main(String args[]) throws NumberFormatException, IOException{
Scanner sc=new Scanner();
while(true){
L=sc.nextInt();
S=sc.nextInt();
K=sc.nextInt();
if (L==0) return;
for(int i=0;i<S;i++)
chips[i]=new point(sc.nextInt(),sc.nextInt());
point[] p=initpoly(L);
ArrayList<point[]> array=new ArrayList<point[]>();
array.add(p);
ArrayList<point[]> tmp;
for(int i=0;i<K;i++){
tmp=new ArrayList<point[]>();
point[] line=new point[2];
line[0]=new point(sc.nextInt(),sc.nextInt());
line[1]=new point(sc.nextInt(),sc.nextInt());
for(point[] poly: array){
point[][] result=bisection(line, poly);
for(int j=0;j<result.length;j++)
tmp.add(result[j]);
}
array=tmp;
//dbg
/*
for(point[] poly: array)
dbg(poly);*/
}
double max=-1;
for(point[] poly: array){
//dbg(poly);
int nchips=0;
for(int i=0;i<S;i++)
if (insidepolygon(poly,poly.length,chips[i]))
nchips++;
double area=polygonarea(poly,poly.length);
double value=nchips/area;
max=Math.max(max, value);
}
System.out.printf("%.3f\n",max);
}
}
}