2022/round3/zero_crossings_ch1.java

import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;

public class ZeroCrossingsCh1 {
  static double globalX = 0;

  static void solve(Scanner fs, PrintWriter out, int tt) {
    int nHulls = fs.nextInt();
    Hull[] hulls = new Hull[nHulls + 1];
    for (int i = 0; i < nHulls; i++) {
      hulls[i] = new Hull(fs);
    }
    hulls[nHulls] = new Hull();
    for (int i = 0; i <= nHulls; i++) {
      hulls[i].id = i;
    }
    ArrayList < Event > events = new ArrayList<>();
    for (Hull h: hulls) {
      events.addAll(h.getEvents());
    }

    int nQ = fs.nextInt();
    Query[] queries = new Query[nQ];
    for (int qq = 0; qq < nQ; qq++) {
      queries[qq] = new Query(fs);
      events.addAll(queries[qq].getEvents());
    }
    Collections.sort(events);

    TreeSet<Seg> set = new TreeSet<>((a, b) -> {
      double ay = a.evalAt(globalX),
      by = b.evalAt(globalX);
      return Double.compare(ay, by);
    });
    for (Event e: events) {
      globalX = e.x;
      if (e.qp != null) {
        Vec position = e.qp.position;
        Seg hSeg = new Seg(position, position.add(new Vec(1, 0)));
        Seg higher = set.higher(hSeg);
        e.qp.node = parent(higher, hulls[nHulls]);
      } else {
        if (e.isEval) {
          Seg higher = set.higher(e.s);
          e.s.hull.parent = parent(higher, hulls[nHulls]);
          e.s.hull.parent.children.add(e.s.hull);
        } else if (e.isStart) {
          set.add(e.s);
        } else {
          set.remove(e.s);
        }
      }
    }
    hulls[nHulls].calcSubtreeHash();
    hulls[nHulls].calcAllHash(new HarmeyerHash(), new HarmeyerHash());

    int ans = 0;
    for (Query qq: queries) {
      Hull node1 = qq.qp1.node, node2 = qq.qp2.node;
      boolean possible = node1.allHash.equals(node2.allHash);
      if (possible) ans++;
    }
    out.println("Case #" + tt + ": " + ans);
  }

  static Hull parent(Seg higher, Hull rootHull) {
    if (higher == null) {
      return rootHull;
    } else if (higher.isUpper) {
      //father
      return higher.hull;
    } else {
      //brother
      return higher.hull.parent;
    }
  }

  // at a particular x:
  // query points (-0.3)
  // removals (-0.1)
  // additions(+0.1)
  // evals(+0.3)
  static class Event implements Comparable < Event > {
    double x,
    y;
    boolean isStart;
    boolean isEval;
    Seg s;
    QueryPoint qp;
    public Event(boolean isStart, Seg s, QueryPoint qp, boolean isEval) {
      this.isStart = isStart;
      this.isEval = isEval;
      this.s = s;
      this.qp = qp;
      if (this.s == null) {
        x = qp.position.x - 0.3;
      } else {
        if (isStart) {
          x = s.from.x + 0.1;
        } else if (isEval) {
          x = s.from.x + 0.3;
          y = s.from.y;
        } else {
          x = s.to.x - 0.1;
        }
      }
    }
    public int compareTo(Event o) {
      if (x != o.x) return Double.compare(x, o.x);
      //process higher y first, since we look upwards
      return Double.compare(o.y, y);
    }
  }

  static class Hull implements Comparable < Hull > {
    int nPoints;
    Vec[] points;
    Vec[] upperHull,
    lowerHull;
    Seg[] upperHullSegs,
    lowerHullSegs;
    int id;

    Hull parent;
    ArrayList < Hull > children = new ArrayList<>();
    HarmeyerHash subtreeHash;
    HarmeyerHash allHash;

    //root hull
    public Hull() {}

    public Hull(Scanner fs) {
      nPoints = fs.nextInt();
      points = new Vec[nPoints];
      for (int i = 0; i < nPoints; i++) {
        points[i] = new Vec(fs.nextInt(), fs.nextInt());
      }
      if (area() < 0) {
        Vec[] newPoints = new Vec[nPoints];
        for (int i = 0; i < nPoints; i++) newPoints[i] = points[nPoints - 1 - i];
        points = newPoints;
      }
      Vec[] sorted = points.clone();
      Arrays.sort(sorted, (a, b) -> {
        if (a.x != b.x) return Double.compare(a.x, b.x);
        return Double.compare(a.y, b.y);
      });
      int leftInd = 0, rightInd = 0;
      for (int i = 0; i < nPoints; i++)
        if (points[i] == sorted[0]) leftInd = i;
      for (int i = 0; i < nPoints; i++)
        if (points[i] == sorted[nPoints - 1]) rightInd = i;
      if (rightInd < leftInd) rightInd += nPoints;
      lowerHull = new Vec[rightInd - leftInd + 1];
      for (int i = leftInd; i <= rightInd; i++) lowerHull[i - leftInd] = points[i % nPoints];

      while (leftInd < rightInd) leftInd += nPoints;
      upperHull = new Vec[leftInd - rightInd + 1];
      for (int i = rightInd; i <= leftInd; i++) upperHull[leftInd - i] = points[i % nPoints];

      upperHullSegs = new Seg[upperHull.length - 1];
      for (int i = 0; i + 1 < upperHull.length; i++) upperHullSegs[i] = new Seg(upperHull[i], upperHull[i + 1]);
      lowerHullSegs = new Seg[lowerHull.length - 1];
      for (int i = 0; i + 1 < lowerHull.length; i++) lowerHullSegs[i] = new Seg(lowerHull[i], lowerHull[i + 1]);

      for (Seg s: upperHullSegs) {
        s.isUpper = true;
        s.hull = this;
      }
      for (Seg s: lowerHullSegs) {
        s.isUpper = false;
        s.hull = this;
      }
    }

    double area() {
      double area = 0;
      for (int i = 0; i < points.length; i++) {
        area += points[i].cross(points[(i + 1) % nPoints]);
      }
      return area / 2;
    }

    // Add events for all lines which aren't vertical.
    ArrayList < Event > getEvents() {
      if (nPoints == 0) {
        // Root query.
        return new ArrayList<>();
      }
      ArrayList < Event > res = new ArrayList<>();
      Seg firstUpper = null;
      for (Seg s: upperHullSegs) {
        if (s.isVertical()) continue;
        if (firstUpper == null) firstUpper = s;
        res.add(new Event(true, s, null, false));
        res.add(new Event(false, s, null, false));
      }
      for (Seg s: lowerHullSegs) {
        if (s.isVertical()) continue;
        res.add(new Event(true, s, null, false));
        res.add(new Event(false, s, null, false));
      }
      res.add(new Event(false, firstUpper, null, true));
      return res;
    }

    void calcSubtreeHash() {
      for (Hull hh: children) {
        hh.calcSubtreeHash();
      }
      Collections.sort(children);
      HarmeyerHash me = new HarmeyerHash();
      me.add('(');
      for (Hull hh: children) {
        me.append(hh.subtreeHash);
      }
      me.add(')');
      this.subtreeHash = me;
    }

    void calcAllHash(HarmeyerHash prefix, HarmeyerHash suffix) {
      prefix = prefix.clone();
      suffix = suffix.clone();
      allHash = new HarmeyerHash();
      allHash.add('s');
      allHash.append(prefix);
      allHash.add('S');
      allHash.append(subtreeHash);
      allHash.add('e');
      allHash.append(suffix);
      allHash.add('E');
      // Now we need to calculate this for our kids
      prefix.add('('); {
        HarmeyerHash temp = new HarmeyerHash();
        temp.add(')');
        temp.append(suffix);
        suffix = temp;
      }
      HarmeyerHash[] subtreesCS = new HarmeyerHash[children.size() + 1];
      subtreesCS[0] = new HarmeyerHash();
      for (int i = 1; i <= children.size(); i++) {
        subtreesCS[i] = subtreesCS[i - 1].clone();
        subtreesCS[i].append(children.get(i - 1).subtreeHash);
      }
      for (int at = 0; at < children.size(); at++) {
        int countIdentical = 1;
        while (at + countIdentical < children.size() &&
              children.get(at + countIdentical).subtreeHash.equals(
                  children.get(at).subtreeHash)) {
          countIdentical++;
        }
        HarmeyerHash beforeGroup = subtreesCS[at];
        HarmeyerHash afterMe = subtreesCS[children.size()].clone();
        afterMe.subHash(subtreesCS[at + 1]);
        HarmeyerHash groupPrefix = prefix.clone();
        groupPrefix.append(beforeGroup);
        HarmeyerHash groupSuffix = afterMe.clone();
        groupSuffix.append(suffix);
        for (int inGroup = 0; inGroup < countIdentical; inGroup++) {
          children.get(at + inGroup).calcAllHash(groupPrefix, groupSuffix);
        }
        at += countIdentical - 1;
      }
    }

    public int compareTo(Hull o) {
      return subtreeHash.compareTo(o.subtreeHash);
    }
  }

  static class QueryPoint {
    Query q;
    Vec position;
    Hull node;
    public QueryPoint(Query q, Vec p) {
      this.q = q;
      this.position = p;
    }
    Event getEvent() {
      return new Event(false, null, this, false);
    }
  }

  static class Query {
    QueryPoint qp1, qp2;
    public Query(Scanner fs) {
      Vec p1 = new Vec(fs.nextInt(), fs.nextInt());
      Vec p2 = new Vec(fs.nextInt(), fs.nextInt());
      qp1 = new QueryPoint(this, p1);
      qp2 = new QueryPoint(this, p2);
    }
    ArrayList < Event > getEvents() {
      ArrayList < Event > res = new ArrayList<>();
      res.add(qp1.getEvent());
      res.add(qp2.getEvent());
      return res;
    }
  }

  static class VecL implements Comparable < VecL > {
    long x, y;

    public VecL(long x, long y) {
      this.x = x;
      this.y = y;
    }

    public VecL add(VecL o) {
      return new VecL(x + o.x, y + o.y);
    }

    public VecL sub(VecL o) {
      return new VecL(x - o.x, y - o.y);
    }

    public VecL scale(long s) {
      return new VecL(x * s, y * s);
    }

    public long dot(VecL o) {
      return x * o.x + y * o.y;
    }

    public long cross(VecL o) {
      return x * o.y - y * o.x;
    }

    public long mag2() {
      return dot(this);
    }

    public VecL rot90() {
      return new VecL(-y, x);
    }

    public VecL rot270() {
      return new VecL(y, -x);
    }

    public String toString() {
      return "(" + x + ", " + y + ")";
    }

    public int hashCode() {
      return Long.hashCode(x << 13 ^ (y * 57));
    }

    public boolean equals(Object oo) {
      VecL o = (VecL) oo;
      return x == o.x && y == o.y;
    }

    public int compareTo(VecL o) {
      if (x != o.x) return Long.compare(x, o.x);
      return Long.compare(y, o.y);
    }

    // origin->q1, axes-> quadrant in ccw direction
    public int quadrant() {
      if (x == 0 || y == 0) {
        if (y == 0) {
          return x >= 0 ? 1 : 3;
        }
        return y >= 0 ? 2 : 4;
      }
      if (x > 0) {
        return y > 0 ? 1 : 4;
      }
      return y > 0 ? 2 : 3;
    }

    public int radialCompare(VecL o) {
      if (quadrant() == o.quadrant()) {
        return -Long.signum(cross(o));
      }
      return Integer.compare(quadrant(), o.quadrant());
    }
  }

  static class Vec {
    static final double EPS = 1e-6;

    double x, y;

    public Vec(double x, double y) {
      this.x = x;
      this.y = y;
    }

    public Vec add(Vec o) {
      return new Vec(x + o.x, y + o.y);
    }

    public Vec sub(Vec o) {
      return new Vec(x - o.x, y - o.y);
    }

    public Vec scale(double s) {
      return new Vec(x * s, y * s);
    }

    public double dot(Vec o) {
      return x * o.x + y * o.y;
    }

    public double cross(Vec o) {
      return x * o.y - y * o.x;
    }

    public double mag2() {
      return dot(this);
    }

    public double mag() {
      return Math.sqrt(mag2());
    }

    public Vec unit() {
      return scale(1 / mag());
    }

    public Vec rot90() {
      return new Vec(-y, x);
    }

    public Vec rot270() {
      return new Vec(y, -x);
    }

    public Vec rotate(double theta) {
      double PI = Math.PI;
      double newX = x * Math.cos(theta) + y * Math.cos(PI / 2 + theta);
      double newY = x * Math.sin(theta) + y * Math.sin(PI / 2 + theta);
      return new Vec(newX, newY);
    }

    // Angle between 0 and 2PI
    public double angle() {
      return (Math.atan2(y, x) + 2 * Math.PI) % (2 * Math.PI);
    }

    public String toString() {
      DecimalFormat df = new DecimalFormat("#.##");
      return "(" + df.format(x) + ", " + df.format(y) + ")";
    }

    static boolean eq(double a, double b) {
      return Math.abs(a - b) < EPS;
    }

    static boolean leq(double a, double b) {
      return a - EPS < b;
    }

    static boolean geq(double a, double b) {
      return a + EPS > b;
    }

    public boolean equals(Object oo) {
      Vec o = (Vec) oo;
      return eq(x, o.x) && eq(y, o.y);
    }
  }


  static class Seg {
    Vec from, to, dir;
    Hull hull;
    boolean isUpper;

    double m, b;

    public Seg(Vec from, Vec to) {
      this.from = from;
      this.to = to;
      dir = to.sub(from);
      if (!isVertical()) {
        m = dir.y / dir.x;
        b = from.y - m * from.x;
      }
    }

    boolean isVertical() {
      return Math.abs(dir.x) < 0.5;
    }

    double evalAt(double x) {
      return m * x + b;
    }

    //line-line intersection
    public Vec lineIntersect(Seg o) {
      double det = o.dir.x * dir.y - dir.x * o.dir.y;
      if (Vec.eq(det, 0)) {
        return null;
      }
      double dist = (o.dir.x * (o.from.y - from.y) -
                     o.dir.y * (o.from.x - from.x)) / det;
      return from.add(dir.scale(dist));
    }

    public boolean containsPoint(Vec o) {
      double distFromLine = dir.unit().cross(o.sub(from));
      if (!Vec.eq(distFromLine, 0)) {
        return false;
      }
      return Vec.eq(dir.mag(), from.sub(o).mag() + to.sub(o).mag());
    }

    // seg-seg intersection
    public Vec segIntersection(Seg o) {
      Vec intersect = lineIntersect(o);
      if (intersect == null) {
        return null;
      }
      return containsPoint(intersect) && o.containsPoint(intersect) ? intersect
                                                                    : null;
    }

    // returns 1 if above, 0 if on, -1 if below
    public int side(Vec o) {
      Vec oDir = o.sub(from);
      double distFromLine = dir.unit().cross(oDir);
      if (Vec.eq(distFromLine, 0)) {
        return 0;
      }
      return (int)Math.signum(distFromLine);
    }

    public boolean intersects(Seg o) {
      return side(o.from) != side(o.to) && o.side(from) != o.side(to);
    }

    public Vec getClosestTo(Vec o) {
      double percentThere = o.sub(from).dot(dir) / dir.mag2();
      return from.add(dir.scale(Math.max(0, Math.min(1, percentThere))));
    }

    public Vec projectToLine(Vec o) {
      return dir.scale(o.sub(from).dot(dir) / dir.mag2()).add(from);
    }

    // toContain must be a point with positive x and y coordinates.
    // this method returns the shortest line segment from the x-axis to the
    // point to the y axis
    public static Seg getShortestSegFromAxesContainingQ1Point(Vec toContain) {
      double slope = -Math.pow(toContain.y / toContain.x, 1.0 / 3);
      double b = toContain.y - toContain.x * slope;
      double xInt = -b / slope;
      return new Seg(new Vec(0, b), new Vec(xInt, 0));
    }

    public String toString() {
      return from + " -> " + to;
    }
  }

  public static void main(String[] args) throws InterruptedException {
    Thread t = new Thread(null, null, "", 1 << 29) {
      public void run() {
        A(null);
      }
    };
    t.start();
    t.join();
  }

  public static void A(String[] args) {
    Scanner fs = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    long time = System.currentTimeMillis();
    int T = fs.nextInt();
    for (int tt = 0; tt < T; tt++) {
      solve(fs, out, tt + 1);
    }
    fs.close();
    out.close();
  }

  // Cannot use 0 as a character in the strings
  static class HarmeyerHash implements Comparable < HarmeyerHash > {
    static final long m1 = 8675309, m2 = 1_000_000_007, m3 = 1_000_000_009;
    long v1 = 0, v2 = 0, v3;
    int l = 0;
    static final long s1 = 257, s2 = 619, s3 = 10007;
    static long[] s1Pow, s2Pow, s3Pow;
    static boolean precomped = false;

    void add(char o) {
      v1 = (v1 * s1 + o) % m1;
      v2 = (v2 * s2 + o) % m2;
      v3 = (v3 * s3 + o) % m3;
      l++;
    }

    void subHash(HarmeyerHash smallerPrefix) {
      HarmeyerHash old = this;
      HarmeyerHash toSub = smallerPrefix;
      int diff = this.l - smallerPrefix.l;
      old.v1 = (old.v1 - (toSub.v1 * s1Pow[diff]) % m1 + m1) % m1;
      old.v2 = (old.v2 - (toSub.v2 * s2Pow[diff]) % m2 + m2) % m2;
      old.v3 = (old.v3 - (toSub.v3 * s3Pow[diff]) % m3 + m3) % m3;
      l = diff;
    }

    public int compareTo(HarmeyerHash o) {
      if (v1 != o.v1) {
        return Long.compare(v1, o.v1);
      }
      if (v2 != o.v2) {
        return Long.compare(v2, o.v2);
      }
      return Long.compare(v3, o.v3);
    }

    public boolean equals(Object o) {
      return compareTo((HarmeyerHash) o) == 0;
    }

    public int hashCode() {
      return (int)v1;
    }

    public HarmeyerHash clone() {
      HarmeyerHash toReturn = new HarmeyerHash();
      toReturn.v1 = v1;
      toReturn.v2 = v2;
      toReturn.v3 = v3;
      toReturn.l = l;
      return toReturn;
    }

    static void precomp() {
      if (precomped) {
        return;
      }
      precomped = true;
      s1Pow = new long[10_000_000];
      s2Pow = new long[10_000_000];
      s3Pow = new long[10_000_000];
      s1Pow[0] = s2Pow[0] = s3Pow[0] = 1;
      for (int i = 1; i < s1Pow.length; i++) {
        s1Pow[i] = (s1Pow[i - 1] * s1) % m1;
      }
      for (int i = 1; i < s2Pow.length; i++) {
        s2Pow[i] = (s2Pow[i - 1] * s2) % m2;
      }
      for (int i = 1; i < s3Pow.length; i++) {
        s3Pow[i] = (s3Pow[i - 1] * s3) % m3;
      }
    }

    //need fastPow if o can be longer than 10^6
    void append(HarmeyerHash o) {
      precomp();
      v1 = (v1 * s1Pow[o.l] + o.v1) % m1;
      v2 = (v2 * s2Pow[o.l] + o.v2) % m2;
      v3 = (v3 * s3Pow[o.l] + o.v3) % m3;
      l += o.l;
    }

    public static HarmeyerHash[] getPrefixHashes(char[] word) {
      precomp();
      int n = word.length;
      HarmeyerHash[] toReturn = new HarmeyerHash[n + 1];
      toReturn[0] = new HarmeyerHash();
      for (int i = 1; i <= n; i++) {
        toReturn[i] = toReturn[i - 1].clone();
        toReturn[i].add(word[i - 1]);
      }
      return toReturn;
    }

    //inclusive, exclusive
    public static HarmeyerHash substringHash(HarmeyerHash[] prefixHashes, int from, int to) {
      if (from == to) {
        return new HarmeyerHash();
      }
      HarmeyerHash old = prefixHashes[to].clone(), toSub = prefixHashes[from];
      int diff = to - from;
      old.v1 = (old.v1 - (toSub.v1 * s1Pow[diff]) % m1 + m1) % m1;
      old.v2 = (old.v2 - (toSub.v2 * s2Pow[diff]) % m2 + m2) % m2;
      old.v3 = (old.v3 - (toSub.v3 * s3Pow[diff]) % m3 + m3) % m3;
      old.l = to - from;
      return old;
    }

    public String toString() {
      return "[" + v1 + " " + v2 + " " + v3 + "]";
    }
  }
}