Created
April 2, 2023 22:31
-
-
Save jlam55555/796b7bb8d26bac515b413d866adfd043 to your computer and use it in GitHub Desktop.
ICPC HS problem from https://gist.github.com/drey7925/98c9de430b33db7c3f603af882c32693
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment