import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Collection; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedList; import java.util.StringTokenizer; /** * ACM ICPC - CERC 2011 * * Sample solution: Unchanged Picture (unchange) * * The similarity detection works as follows: one of the line segments from * the first picture is mapped to all segments of the other picture in sequence. * For each mapping, we verify whether all segments have their counterparts. * * No floating-point arithmetics needed. ;-) * * Quadratic time. * As mentioned in the problem notes, faster solution is possible. * * @author Martin Kacer */ public class unchange { StringTokenizer st = new StringTokenizer(""); BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws Exception { unchange inst = new unchange(); while (inst.run()) {/* nothing */} } String nextToken() throws Exception { while (!st.hasMoreTokens()) st = new StringTokenizer(input.readLine()); return st.nextToken(); } int nextInt() throws Exception { return Integer.parseInt(nextToken()); } /** Two-dimensional point. */ static class Point implements Comparable { final int x, y; Point(int x, int y) { this.x = x; this.y = y; } public int compareTo(Point o) { return (this.x == o.x) ? this.y - o.y : this.x - o.x; } Point diff(Point o) { return new Point(this.x - o.x, this.y - o.y); } @Override public int hashCode() { return (31 + x) * 31 + y; } @Override public boolean equals(Object obj) { if (!(obj instanceof Point)) return false; Point o = (Point)obj; return (this.x == o.x) && (this.y == o.y); } } /** 2D line segment. The order of its endpoints is normalized. */ static class Line { final Point a, b; Line(Point a, Point b) { if (a.compareTo(b) <= 0) { this.a = a; this.b = b; } else { this.a = b; this.b = a; } } @Override public int hashCode() { return (31 + a.hashCode()) * 31 + b.hashCode(); } @Override public boolean equals(Object obj) { if (!(obj instanceof Line)) return false; Line o = (Line)obj; return this.a.equals(o.a) && this.b.equals(o.b); } } Point minPoint(Point a, Point b) { return a.compareTo(b) < 0 ? a : b; } Point maxPoint(Point a, Point b) { return a.compareTo(b) >= 0 ? a : b; } /** Tell whether two vectors are parallel/colinear. */ boolean parallel(int ax, int ay, int bx, int by) { return (long)ax * by == (long)ay * bx; } /** Tell whether two lines are colinear (lying in the same infinite line). */ boolean colinear(Line n, Line m) { return parallel(n.b.x - n.a.x, n.b.y - n.a.y, m.b.x - m.a.x, m.b.y - m.a.y) && parallel(n.b.x - n.a.x, n.b.y - n.a.y, m.a.x - n.a.x, m.a.y - n.a.y); } Collection pic1, pic2; boolean run() throws Exception { pic1 = new LinkedList(); pic2 = new HashSet(); Collection cur = pic1; Point p = new Point(0,0); for (;;) { String cmd = nextToken(); if ("Q".equals(cmd)) return false; if ("E".equals(cmd)) { if (cur != pic1) break; p = new Point(0,0); cur = pic2; continue; } int dx = nextInt(), dy = nextInt(); Point q = new Point(p.x+dx, p.y+dy); if ("L".equals(cmd)) { addLine(cur, new Line(p, q)); } p = q; } if (pic1.size() != pic2.size()) { System.out.println("NO"); return true; } Line n = null; for (Line m : pic1) { n = m; break; } if (n == null) { System.out.println("YES"); return true; } // try one line against all lines from the other picture for (Line m : pic2) if (matchPicture(n.a, n.b, m) || matchPicture(n.b, n.a, m)) { System.out.println("YES"); return true; } System.out.println("NO"); return true; } /** Add line to a collection. * Merge it with all existing colinear lines that have non-empty intersection. */ void addLine(Collection lines, Line n) { Iterator it = lines.iterator(); while (it.hasNext()) { Line e = it.next(); if (!colinear(n, e)) continue; if (n.b.compareTo(e.a) < 0) continue; if (e.b.compareTo(n.a) < 0) continue; it.remove(); n = new Line(minPoint(n.a, e.a), maxPoint(n.b, e.b)); } lines.add(n); } /** Verify whether the pictures match using the transformation * mapping oa--ob to n.a--n.b. * (we cannot use Line for one pair, because it normalizes the order) */ boolean matchPicture(Point oa, Point ob, Line n) { for (Line m : pic1) { Point ma = transformPoint(oa, ob, n, m.a.x, m.a.y); Point mb = transformPoint(oa, ob, n, m.b.x, m.b.y); if (ma == null || mb == null) return false; if (!pic2.contains(new Line(ma, mb))) return false; } return true; } /** * Transform the point (x,y) with a transformation defined by * a source vector (oa.x,oa.y)-(ob.x,ob.y) * and a corresponding target vector (n.a.x,n.a.y)-(n.b.x,n.b.y) * @return a transformed point or null, if it has not integer coordinates. */ Point transformPoint(Point oa, Point ob, Line n, int x, int y) { long lensq = (long)(ob.x-oa.x)*(ob.x-oa.x) + (long)(ob.y-oa.y)*(ob.y-oa.y); Point nd = n.b.diff(n.a); long xx = (long)(x-oa.x)*(ob.x-oa.x)*nd.x + (long)(x-oa.x)*(ob.y-oa.y)*nd.y - (long)(y-oa.y)*(ob.x-oa.x)*nd.y + (long)(y-oa.y)*(ob.y-oa.y)*nd.x; long yy = (long)(x-oa.x)*(ob.x-oa.x)*nd.y - (long)(x-oa.x)*(ob.y-oa.y)*nd.x + (long)(y-oa.y)*(ob.x-oa.x)*nd.x + (long)(y-oa.y)*(ob.y-oa.y)*nd.y; // the resulting point is now: (xx/lensq + n.a.x, yy/lensq + n.a.y) if (xx % lensq != 0 || yy % lensq != 0) return null; return new Point((int)(xx/lensq) + n.a.x, (int)(yy/lensq) + n.a.y); } }