import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.ArrayList; import java.util.BitSet; import java.util.Comparator; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.StringTokenizer; /** * ICPC Central Europe Regional Contest 2018 * Sample solution: Mirrority Report * "Exact arithmetic" version. (!) * * Unlike other solutions, this does not try all permutations. * Instead, we only follow possible reflections and run a BFS over them. * A single unit is called a "sector", it corresponds to a widening "beam" * with a triangular shape - the solution may run anywhere inside the sector. *
* This was originally intended for a different version of the problem,
* where the minimal number of reflections should be computed.
* For that version, this solutions runs very fast for most test cases,
* yet it's worst-case is difficult to find.
*
* @author Martin Kacer
*/
public class MirrorityReportBigRational {
StringTokenizer st = new StringTokenizer("");
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
boolean hasNextToken() {
try {
while (!st.hasMoreTokens()) {
String line = input.readLine();
if (line == null) return false;
st = new StringTokenizer(line);
}
} catch (IOException ex) { throw new RuntimeException(ex); }
return true;
}
String nextToken() {
return (!hasNextToken()) ? null : st.nextToken();
}
int nextInt() {
return Integer.parseInt(nextToken());
}
public static void main(String[] args) {
new MirrorityReportBigRational().run();
}
static final double EPS = 1E-5;
static class Num {
final BigInteger num, den;
Num(BigInteger n, BigInteger d) { BigInteger g = n.gcd(d); num = n.divide(g); den = d.divide(g); }
Num add(Num n) { return new Num(this.num.multiply(n.den).add(n.num.multiply(this.den)), this.den.multiply(n.den)); }
Num sub(Num n) { return new Num(this.num.multiply(n.den).subtract(n.num.multiply(this.den)), this.den.multiply(n.den)); }
Num mul(Num n) { return new Num(this.num.multiply(n.num), this.den.multiply(n.den)); }
Num div(Num n) { return new Num(this.num.multiply(n.den), this.den.multiply(n.num)); }
Num mul(int i) { return new Num(this.num.multiply(BigInteger.valueOf(i)), this.den); }
boolean eq(Num n) { return this.sub(n).num.equals(BigInteger.ZERO); }
boolean pos() { return this.num.signum() == this.den.signum(); }
Num abs() { return pos() ? this : new Num(this.num.negate(), this.den); }
double atan2(Num y) { return Math.atan2(y.doubleValue(), this.doubleValue()); }
double doubleValue() { return this.num.doubleValue() / this.den.doubleValue(); }
@Override public String toString() { return String.valueOf(this.doubleValue()); }
}
static Num num(int x) { return new Num(BigInteger.valueOf(x), BigInteger.ONE); }
static final Num ZERO = num(0), MAX2 = num(200), MAX2N = MAX2.mul(-1);
static class Point {
Num x, y;
Point(Num x, Num y) { this.x = x; this.y = y; }
@Override public String toString() { return "[" + this.x + "," + this.y + "]"; }
}
static Point mirror(Point a, Point b, Point p) {
Num xba = b.x.sub(a.x), yba = b.y.sub(a.y), xpa = p.x.sub(a.x), ypa = p.y.sub(a.y);
Num xba2 = xba.mul(xba), yba2 = yba.mul(yba);
Num len = xba2.add(yba2);
Num xq = xba.mul(ypa).mul(yba).sub(yba2.mul(xpa)) .mul(2).div(len).add(p.x);
Num yq = xba2.mul(ypa).sub(yba.mul(xpa).mul(xba)) .mul(-2).div(len).add(p.y);
return new Point(xq, yq);
}
static Num cross(Point p1, Point p2, Point p3, Point p4) {
return p2.x.sub(p1.x).mul(p4.y.sub(p3.y)).sub( p2.y.sub(p1.y).mul(p4.x.sub(p3.x)) );
}
static Point intersect(Point p1, Point p2, Point p3, Point p4) {
Num x21 = p2.x.sub(p1.x), y21 = p2.y.sub(p1.y), x43 = p4.x.sub(p3.x), y43 = p4.y.sub(p3.y);
Num d0 = y43.mul(x21).sub( x43.mul(y21) );
if (d0.eq(ZERO)) return null;
Num x13 = p1.x.sub(p3.x), y13 = p1.y.sub(p3.y);
Num dA = x43.mul(y13).sub( y43.mul(x13) ), tA = dA.div(d0);
return new Point(p1.x.add( x21.mul(tA) ), p1.y.add( y21.mul(tA) ));
}
class Sector {
final Point ct, lf, rg;
final BitSet use;
Sector(Point c, Point l, Point r, BitSet u) {
this.ct = c; this.lf = l; this.rg = r; this.use = u;
}
@Override public String toString() { return "SECT:" + ct + ":" + lf + "-" + rg + ":" + use; }
}
int lines, answers = 0;
Point start, goal;
Point[] line1, line2;
Point[][] isect;
Queue