ICPC HS problem from https://gist.github.com/drey7925/98c9de430b33db7c3f603af882c32693

Problem7.cpp

#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <tuple>
#include <vector>

// m total lines, v + h = m
// O(v^2 * h*log(h))
//
// v*h + (v-1)*(h-1) + (v-2)*(h-2) + ... + 1*1
// something like cubic
struct Segment {
  int x0;
  int y0;
  int x1;
  int y1;
};

// Interval is represented by a tuple
// (value on perpendicular axis, start, end)
using Interval = std::tuple<int, int, int>;

std::ostream &operator<<(std::ostream &os, Interval i) {
  auto [perp, s, e]{i};
  return os << "[" << perp << ", " << s << ":" << e << "]";
}

void Merge(std::vector<Interval> &intervals) {
  // Lexicographic sort.
  std::sort(intervals.begin(), intervals.end());
  int len{};
  for (int i{}, n(intervals.size()); i < n;) {
    auto [curr_perpendicular, start, end] = intervals[i];

    int j{i + 1};
    while (j < n && std::get<0>(intervals[j]) == curr_perpendicular &&
           std::get<1>(intervals[j]) <= end) {
      end = std::max(end, std::get<2>(intervals[j]));
      ++j;
    }

    intervals[len++] = std::make_tuple(curr_perpendicular, start, end);
    i = j;
  }

  intervals.resize(len);
}

int OverlapLen(int s0, int e0, int s1, int e1) {
  return std::min(e0, e1) - std::max(s0, s1);
}

int CountSquares(const std::vector<Segment> &segments) {
  // Separate into vertical and horizontal lines.
  std::vector<Interval> ver, hor;
  for (const auto &segment : segments) {
    if (segment.x0 == segment.x1) {
      ver.push_back({segment.x0, segment.y0, segment.y1});
    } else {
      hor.push_back({segment.y0, segment.x0, segment.x1});
    }
  }

  // Merge all horizontal and vertical lines
  // that are overlapping in the same direction.
  Merge(ver);
  Merge(hor);

  std::unordered_map<int, std::vector<Interval>> hor_lookup;
  for (const auto &interval : hor) {
    hor_lookup[std::get<0>(interval)].push_back(interval);
  }

  // Loop through pairs of vertical lines,
  // horizontal distance of n between them.
  // Horizontal lines at x1, x2, |x1-x2| = n.
  //
  //    Linear pass through horizontal lines,
  //    find all other horizontal lines that are n
  //    distance apart.
  //    We have a line at y1. Make sure that this
  //    line intersects both vl1, vl2.
  //    Look at all lines at hl1s = {y1-n}
  //
  //    Do a binary search to find the first line that
  //    intersects vl1 and vl2.
  int h(hor.size()), v(ver.size()), res{};
  for (int v0{}; v0 < v; ++v0) {
    for (int v1{v0 + 1}; v1 < v; ++v1) {
      auto [x0, vs0, ve0] = ver[v0];
      auto [x1, vs1, ve1] = ver[v1];

      // Make sure there is some overlap between (v0, v1)
      if (OverlapLen(vs0, ve0, vs1, ve1) <= 0) {
        continue;
      }

      int n{x1 - x0};
      for (int h0{}; h0 < h; ++h0) {
        auto [y0, hs0, he0] = hor[h0];

        // Check that hor[h1] intersects both (v0, v1)
        if ((y0 + n) > std::min(ve0, ve1) /* h1 is too high */
            || y0 < std::max(vs0, vs1)    /* h0 is too low */
            ||
            OverlapLen(hs0, he0, x0, x1) < n /* h0 is too short horizontally */
        ) {
          continue;
        }

        // Find all other horizontal lines at y=y0+n.
        auto h1s_it{hor_lookup.find(y0 + n)};
        if (h1s_it == hor_lookup.end()) {
          continue;
        }
        auto &h1s{h1s_it->second};

        // Binary search, find first horizontal interval at y1=y0+n,
        // such that the start index <= x0.
        auto h1_it{std::upper_bound(h1s.begin(), h1s.end(),
                                    std::make_tuple(y0 + n, x0, INT_MAX))};
        if (h1_it == h1s.begin()) {
          continue;
        }
        --h1_it;
        auto [y1, hs1, he1] = *h1_it;

        // Make sure h1 is not too short horizontally.
        if (OverlapLen(hs1, he1, x0, x1) < n) {
          continue;
        }

        // std::cout << "Found square " << hor[h0] << " " << *h1_it << " "
        //           << ver[v0] << " " << ver[v1] << std::endl;
        ++res;
      }
    }
  }

  return res;
}

int main() {
  std::vector<Segment> tc1{
      // Vertical
      {1, 0, 1, 10},
      {6, 2, 6, 3},
      {6, 3, 6, 9},
      {8, 1, 8, 10},
      // Horizontal
      {0, 2, 10, 2},
      {1, 4, 8, 4},
      {0, 9, 5, 9},
      {3, 9, 10, 9},
  },
      tc2{
          // Vertical
          {1, 0, 1, 10},
          {6, 2, 6, 4},
          {6, 4, 6, 9},
          {8, 1, 8, 10},
          // Horizontal
          {0, 2, 4, 2},
          {5, 2, 10, 2},
          {0, 4, 1, 4},
          {1, 4, 3, 4},
          {2, 4, 6, 4},
          {6, 4, 8, 4},
          {1, 9, 10, 9},
      };

  std::random_shuffle(tc1.begin(), tc1.end());
  std::random_shuffle(tc2.begin(), tc2.end());

  assert(CountSquares(tc1) == 3);
  assert(CountSquares(tc2) == 2);
}