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 queue = new LinkedList<>(); static class AngleComp implements Comparator { final Point ct; final double lim; AngleComp(Sector s) { this.ct = s.ct; this.lim = ((s.lf == null) ? Math.PI : s.lf.x.sub(ct.x).atan2(s.lf.y.sub(ct.y))) + EPS; } public int compare(Point o1, Point o2) { double a1 = o1.x.sub(ct.x).atan2(o1.y.sub(ct.y)), a2 = o2.x.sub(ct.x).atan2(o2.y.sub(ct.y)); return Double.compare(a1, a2) * (int)Math.signum(a1 - lim) * (int)Math.signum(a2 - lim); } } void findIntersections() { for (int i1 = 0; i1 < lines; ++i1) for (int i2 = 0; i2 < lines; ++i2) { isect[i1][i2] = intersect(line1[i1], line2[i1], line1[i2], line2[i2]); } } boolean validate(Num res, boolean edges) { return res.pos() || (edges && res.eq(ZERO)); } boolean isInside(Sector sect, Point p, boolean edges) { if (sect.lf != null) { if (!validate(cross(sect.ct, sect.rg, sect.ct, p), edges)) return false; if (!validate(cross(sect.lf, sect.ct, sect.ct, p), edges)) return false; if (!validate(cross(sect.lf, sect.rg, sect.lf, p), false)) return false; } for (int i = 0; i < lines; ++i) if (sect.use.get(i)) { Num side = cross(line1[i], line2[i], line1[i], (sect.lf != null) ? sect.lf : sect.ct); if (side.eq(ZERO)) side = cross(line1[i], line2[i], line1[i], sect.rg); if (side.eq(ZERO)) continue; Num test = side.pos() ? cross(line1[i], line2[i], line1[i], p) : cross(line2[i], line1[i], line1[i], p); if (!validate(test, edges)) return false; } return true; } void offer(Sector sect, List pts, Point p) { if ((p != null) && isInside(sect, p, true)) pts.add(p); } void offerInfinities(Sector sect, List pts, int idx) { if (line1[idx].x.sub(line2[idx].x).abs().sub( line1[idx].y.sub(line2[idx].y).abs() ).pos()) { offer(sect, pts, intersect(line1[idx], line2[idx], new Point(MAX2, MAX2N), new Point(MAX2, MAX2))); offer(sect, pts, intersect(line1[idx], line2[idx], new Point(MAX2N, MAX2N), new Point(MAX2N, MAX2))); } else { offer(sect, pts, intersect(line1[idx], line2[idx], new Point(MAX2N, MAX2N), new Point(MAX2, MAX2N))); offer(sect, pts, intersect(line1[idx], line2[idx], new Point(MAX2N, MAX2), new Point(MAX2, MAX2))); } } int findLine(BitSet use, Point p, Point q) { for (int i = 0; i < lines; ++i) if (use.get(i)) if (cross(line1[i], line2[i], line1[i], p).eq(ZERO) && cross(line1[i], line2[i], line1[i], q).eq(ZERO)) return i; return -1; } void bfs() { BitSet all = new BitSet(lines); all.set(0, lines); queue.add(new Sector(start, null, null, all)); Sector sect; while ((sect = queue.poll()) != null) { System.err.println("processing: " + sect); if (isInside(sect, goal, false)) { ++answers; System.err.println(" - goal reached"); } // this does not work correctly for some reason: if (isInside(sect, goal, true)) throw new IllegalStateException("corner hit!"); List pts = new ArrayList<>(); for (int i1 = 0; i1 < lines; ++i1) if (sect.use.get(i1)) { if (sect.lf != null) { offer(sect, pts, intersect(sect.ct, sect.lf, line1[i1], line2[i1])); offer(sect, pts, intersect(sect.ct, sect.rg, line1[i1], line2[i1])); } offerInfinities(sect, pts, i1); for (int i2 = i1+1; i2 < lines; ++i2) if (sect.use.get(i2)) offer(sect, pts, isect[i1][i2]); } if (pts.isEmpty()) continue; pts.sort(new AngleComp(sect)); System.err.println(" - points: " + pts); if (sect.lf == null) { pts.add(pts.get(0)); } else { if (!cross(sect.ct, sect.rg, sect.ct, pts.get(0)).eq(ZERO)) pts.add(0, sect.rg); if (!cross(sect.ct, sect.lf, sect.ct, pts.get(pts.size()-1)).eq(ZERO)) pts.add(sect.lf); } System.err.println(" - points: " + pts); for (int i = 0; i < pts.size() - 1; ++i) { Point p = pts.get(i), q = pts.get(i+1); if (!cross(sect.ct,p, sect.ct,q).pos()) continue; BitSet use2 = (BitSet) sect.use.clone(); int linidx = findLine(sect.use, p, q); if (linidx < 0) continue; use2.clear(linidx); Sector nsect = new Sector(mirror(p, q, sect.ct), p, q, use2); queue.add(nsect); System.err.println(" - adding: " + nsect); } } } void readInput() { lines = nextInt(); start = new Point(num(nextInt()), num(nextInt())); goal = new Point(num(nextInt()), num(nextInt())); line1 = new Point[lines]; line2 = new Point[lines]; isect = new Point[lines][lines]; for (int i = 0; i < lines; ++i) { line1[i] = new Point(num(nextInt()), num(nextInt())); line2[i] = new Point(num(nextInt()), num(nextInt())); } } void run() { readInput(); findIntersections(); bfs(); System.out.println(answers); } }