USACO 2019 US Open Contest Silver Division - Cow Steeplechase II#
Problem link: here
Solution Author: Stefan Dascalescu
Problem Solution#
This is an implementation heavy problem. I recommend checking the code below.
Source code#
The source code in C++ can be seen below. It is based on a code written by GPT with extensive comments.
#include <bits/stdc++.h>
using namespace std;
static const long long INF = 1LL << 60;
struct Segment {
// Store original endpoints
// We'll keep them in the order (x1, y1), (x2, y2) as given,
// but we will often want min_x, max_x, etc. for the sweep.
long long x1, y1, x2, y2;
};
int N;
vector<Segment> segs;
// -------------- Geometry helpers --------------
// Orientation test: returns
// 0 if collinear
// 1 if clockwise (turn right)
// 2 if counterclockwise (turn left)
int orientation(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3) {
// Cross product: (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1)
__int128 cross = (__int128)(x2 - x1) * (y3 - y1) - (__int128)(y2 - y1) * (x3 - x1);
if (cross == 0) return 0;
return (cross > 0 ? 1 : 2);
}
// Check if point (px, py) lies on segment (x1, y1)-(x2, y2)
bool onSegment(long long x1, long long y1, long long x2, long long y2, long long px, long long py) {
// (px,py) should be collinear and within bounding box
if (min(x1, x2) <= px && px <= max(x1, x2) && min(y1, y2) <= py && py <= max(y1, y2)) {
return true;
}
return false;
}
// Check if segments a and b intersect
bool doIntersect(const Segment &a, const Segment &b) {
// Unpack
long long x1 = a.x1, y1 = a.y1, x2 = a.x2, y2 = a.y2;
long long x3 = b.x1, y3 = b.y1, x4 = b.x2, y4 = b.y2;
// Four orientation tests
int o1 = orientation(x1, y1, x2, y2, x3, y3);
int o2 = orientation(x1, y1, x2, y2, x4, y4);
int o3 = orientation(x3, y3, x4, y4, x1, y1);
int o4 = orientation(x3, y3, x4, y4, x2, y2);
// General case
if (o1 != o2 && o3 != o4) return true;
// Special cases: collinear + on-segment
if (o1 == 0 && onSegment(x1, y1, x2, y2, x3, y3)) return true;
if (o2 == 0 && onSegment(x1, y1, x2, y2, x4, y4)) return true;
if (o3 == 0 && onSegment(x3, y3, x4, y4, x1, y1)) return true;
if (o4 == 0 && onSegment(x3, y3, x4, y4, x2, y2)) return true;
return false;
}
// -------------- Sweep line structures --------------
// We'll keep a global "currentX" that indicates where the sweep line is.
// Our comparator for the active segments in the balanced tree will compare
// their "y-position" at currentX.
long long currentX;
// Compute the y-coordinate of segment s at x = currentX (as a long double)
long double getY(const Segment &s, long long x) {
// If the segment is vertical, just return the min(y1,y2) or so.
// But we want the precise "intersection" of the vertical line x with the
// segment. Let's do a safe linear interpolation:
// y = y1 + (y2 - y1) * (x - x1) / (x2 - x1)
// Watch out for division by zero if x1 == x2.
if (s.x1 == s.x2) {
// It's a vertical segment. Just return the lower of y1, y2 if we are
// within range. The sweep line is at currentX = x. If x != s.x1, we
// might still compare but let's just return the lower endpoint to keep
// ordering consistent.
return (long double)min(s.y1, s.y2);
}
// Otherwise do interpolation in long double
long double dx = (long double)(x - s.x1);
long double full = (long double)(s.x2 - s.x1);
long double ratio = dx / full;
return (long double)s.y1 + ratio * (long double)(s.y2 - s.y1);
}
// We'll store only indices in the balanced tree, and compare by y at currentX.
struct ActiveCompare {
bool operator()(int i, int j) const {
if (i == j) return false; // no strict ordering for same element
long double yi = getY(segs[i], currentX);
long double yj = getY(segs[j], currentX);
// Use an epsilon if you like, but normally not strictly needed for an
// integer-based problem
if (fabsl(yi - yj) > 1e-15) {
return yi < yj;
}
// Tie-break by index to have a strict ordering
return i < j;
}
};
// -------------- Sweeping and intersection detection --------------
// We'll define a function that, ignoring one specific segment index (ignoreID),
// returns the first intersecting pair it finds (or {-1, -1} if none).
// If we only want to detect "is there ANY intersection," we can stop at the
// first one.
pair<int, int> findAnyIntersection(int ignoreID = -1) {
// Build events: (x, type, idx)
// type: +1 = start, -1 = end
vector<array<long long, 3>> events;
events.reserve(2 * N);
for (int i = 0; i < N; i++) {
if (i == ignoreID) continue; // skip the ignored segment
long long x1 = segs[i].x1;
long long y1 = segs[i].y1;
long long x2 = segs[i].x2;
long long y2 = segs[i].y2;
// We want start-event at min(x1,x2), end-event at max(x1,x2)
// We'll just store them with type +1 or -1, plus the segment index i.
long long leftX = min(x1, x2);
long long rightX = max(x1, x2);
// Start event
events.push_back({leftX, +1, i});
// End event
events.push_back({rightX, -1, i});
}
// Sort by x; if tie, let end events come before start events to avoid
// spuriously counting adjacency as intersection.
// (Exact tie-breaking may vary; being consistent is what's important.)
sort(events.begin(), events.end(), [&](auto &a, auto &b) {
if (a[0] != b[0]) return a[0] < b[0];
// tie in x => put end(-1) before start(+1)
return a[1] > b[1];
});
// Balanced BST of active segments
set<int, ActiveCompare> active;
// Helper to check intersection between neighbors
auto checkNeighbor = [&](auto it, auto nxt) -> pair<int, int> {
if (it == active.end() || nxt == active.end()) return {-1, -1};
int si = *it, sj = *nxt;
if (doIntersect(segs[si], segs[sj])) {
// Found intersection
return {si, sj};
}
return {-1, -1};
};
// Sweep
for (auto &ev : events) {
long long x = ev[0];
int typ = (int)ev[1];
int idx = (int)ev[2];
// Update currentX for the comparator
currentX = x;
if (typ == +1) {
// Insert idx
auto pos = active.insert(idx).first;
// Check intersection with neighbor above and below
if (pos != active.begin()) {
auto prev = std::prev(pos);
auto res = checkNeighbor(prev, pos);
if (res.first != -1) return res;
}
auto next = std::next(pos);
if (next != active.end()) {
auto res = checkNeighbor(pos, next);
if (res.first != -1) return res;
}
} else {
// Remove idx
// First find it
auto pos = active.find(idx);
if (pos != active.end()) {
// Before removing, check the neighbors to see if they'd now
// intersect
auto prev = (pos == active.begin() ? active.end() : std::prev(pos));
auto nxt = std::next(pos);
if (prev != active.end() && nxt != active.end()) {
auto res = checkNeighbor(prev, nxt);
if (res.first != -1) return res;
}
active.erase(pos);
}
}
}
// No intersection found
return {-1, -1};
}
// -------------- Main solve logic --------------
int main() {
ifstream cin("cowjump.in");
ofstream cout("cowjump.out");
cin >> N;
segs.resize(N);
for (int i = 0; i < N; i++) {
cin >> segs[i].x1 >> segs[i].y1 >> segs[i].x2 >> segs[i].y2;
}
// 1) Find an intersection ignoring no segment
auto firstIntersect = findAnyIntersection(-1);
// If there's no intersection at all (unlikely given problem statement),
// we don't need to remove anything, but the problem states there's always
// an intersection unless we remove one segment. We handle it just in case:
if (firstIntersect.first == -1) {
// No intersection => The problem statement says there's definitely one,
// but let's be safe and just say remove segment 1 (arbitrary).
cout << 1 << "\n";
return 0;
}
int s1 = firstIntersect.first;
int s2 = firstIntersect.second;
if (s1 > s2) std::swap(s1, s2);
// We'll test removing s1 or s2.
// 2) Re-sweep ignoring s1
auto test1 = findAnyIntersection(s1);
bool fixByRemovingS1 = (test1.first == -1);
// 3) Re-sweep ignoring s2
auto test2 = findAnyIntersection(s2);
bool fixByRemovingS2 = (test2.first == -1);
// The problem states removing exactly one segment *will* fix it,
// so at least one of fixByRemovingS1 / fixByRemovingS2 must be true.
// If both are true, we pick the earlier index.
if (fixByRemovingS1 && fixByRemovingS2) {
cout << min(s1 + 1, s2 + 1) << "\n";
} else if (fixByRemovingS1) {
cout << (s1 + 1) << "\n";
} else {
cout << (s2 + 1) << "\n";
}
return 0;
}