/*
slice.java
Any Way You Slice It, MCPC 2012 Problem C
Java solution by Andy Harrington
(implementing low-level math)
*/
import java.io.*;
import java.util.*;
import static java.lang.Math.*;
public class slice
{
static int NMAX = 100;
// side i+1 of length d[i] goes forward at angle a[i] from (x[i], y[i]).
static int[] d = new int[NMAX];
static double[] a = new double[NMAX],
x = new double[NMAX+1],
y = new double[NMAX+1];
static int N; // total segments
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(new File("slice.in"));
N = in.nextInt();
while (N > 0) {
double prevAng = PI/2;
for (int i = 0; i < N; i++) {
prevAng = a[i] = prevAng + in.nextInt()*PI/180;
System.err.format("%f (%f, %f)%n", a[i]*180/PI, x[i], y[i]);
d[i] = in.nextInt();
x[i+1] = x[i] + d[i]*cos(a[i]);
y[i+1] = y[i] + d[i]*sin(a[i]);
}
System.err.format("(%f, %f)%n", x[N], y[N]);
System.out.println(solve());
N = in.nextInt();
}
}
static String solve()
{
for (int i=2; i < N; i++)
if (collide(i))
return ""+(i+1);
return "SAFE";
}
static boolean collide(int i) // true if seg crosses previous segment
{
for (int j = 0; j < i-1; j++) {// stop before previous segment
double uxv = sin(a[j] - a[i]); // math comments at the end
if (abs(uxv) < PI/360) // no bad cases, with endpoint at cross pt
continue; // so do not worry about parallel lines
double t = ((x[j]-x[i])*sin(a[j]) - (y[j]-y[i])*cos(a[j]))/uxv,
s = ((x[j]-x[i])*sin(a[i]) - (y[j]-y[i])*cos(a[i]))/uxv;
if (0 <= min(s, t) && s <= d[j] && t <= d[i])
return true;
}
return false;
}
}
/*
The basic vector line intersection math is simpler here with the angles and
lengths already given:
If p and q are initial segment endpoints and u and v are unit vectors along
them, the lines intersect where there are scalars s, t so p +tu = q + sv
Crossing with v (meaning the scalar z component), we can solve for t:
t = ((q-p) x v) / (u x v), similarly s = ((p - q) x u) / (v x u).
For the intersection points to be on the segments we need
0 <= t <= its segment length, and similarly for s. u and v are just given
by the cos and sin of the segment's angle. Lengths are in the input.
Because we are not allowing the edge cases, I ignore if the two segments
are parallel.
*/
|