One of the first ingredients in this problem is writing code to test whether two segments intersect. This can be done several ways; the preferred method is probably a standard trick using signs of cross products to test whether segment $pq$ intersects segment $rs$ by testing if $p$ and $q$ lie on opposite sides of line $rs$ and $r$ and $s$ lie on opposite sides of line $pq$. If you haven't seen this approach before, you may want to look up further details and add it to your repertoire.
We could solve this problem in $O(n^2)$ time by testing every pair of segments for intersection, but this would be too slow.
To start, let's simplify the problem a little bit, and focus on finding just any pair of intersecting segments. Once we have found these, we are essentially done, since the answer will be one of the two segments --- we just need to count to see if either of the two segments has multiple intersections (in which case it is the answer) or else the lower-index segment is the answer.
To find an intersecting pair of segments, we use what we could call a "plane sweep" or "sweep line" approach. Imagine sweeping a vertical line across the scene from left to right, pausing at every segment endpoint. We simulate this by first sorting all the segment endpoints on $x$ and walking through this sorted array (the array $P$ in my code below). As we scan, we keep track of all segments that are currently "active" in another data structure (called "active" in my code). When we hit the leading point of a segment, we add it to the active set, and when we hit the trailing point of a segment, we remove it from the active set. Since the active set is implemented as an STL set (which is a balanced binary search tree under the hood), every operation so far takes $O(\log n)$ time, for a total of $O(n \log n)$ time, including the initial sort.
Our active set of segments will be ordered by $y$ coordinate. Note that as long as we don't scan across any intersections, the segments will remain consistently ordered in $y$, so comparing two segments gives the same answer during the scan regardless of the $x$ coordinate at which they are evaluated, and therefore our set data structure doesn't get confused. The key insight now is that if two segments intersect, they must at some point be neighbors (i.e, adjacent in $y$) in the active structure. So whenever we insert a new segment, we test for intersection between the segments immediately above and below it (if any) which now become neighbors with the new segment, and whenever we delete a segment, we test for intersection between the segments above and below it, which become neighbors of each-other upon the deletion. The instant we discover any intersection, we stop sweeping.
My code in C++ is below. The segment intersection part is a little bit terse, but this isn't the "important" part of the solution --- it just tests for intersection. The more interesting part of the solution is what follows, where we sort the segments, scan on $x$, and test for intersections along the way while maintaining the active set of segments. The total running time is $O(n \log n)$.
As a note: we designed the test data for this problem so that other heuristic-type approaches would hopefully still receive some partial credit. This problem was definitely towards the higher end of the difficulty scale for a silver problem, hopefully befitting its placement on the US Open contest.
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef long long LL;
int N;
double x;
struct Point { LL x, y; int segindex; };
struct Segment { Point p, q; int index; };
bool operator< (Point p1, Point p2) { return p1.x==p2.x ? p1.y<p2.y : p1.x<p2.x; }
// Intersection testing (here, using a standard "cross product" trick)
int sign(LL x) { if (x==0) return 0; else return x<0 ? -1 : +1; }
int operator* (Point p1, Point p2) { return sign(p1.x * p2.y - p1.y * p2.x); }
Point operator- (Point p1, Point p2) { Point p = {p1.x-p2.x, p1.y-p2.y}; return p; }
bool isect(Segment &s1, Segment &s2)
{
Point &p1 = s1.p, &q1 = s1.q, &p2 = s2.p, &q2 = s2.q;
return ((q2-p1)*(q1-p1)) * ((q1-p1)*(p2-p1)) >= 0 && ((q1-p2)*(q2-p2)) * ((q2-p2)*(p1-p2)) >= 0;
}
// What is the y coordinate of segment s when evaluated at x?
double eval(Segment s) {
if (s.p.x == s.q.x) return s.p.y;
return s.p.y + (s.q.y-s.p.y) * (x-s.p.x) / (s.q.x-s.p.x);
}
bool operator< (Segment s1, Segment s2) { return s1.index != s2.index && eval(s1)<eval(s2); }
bool operator== (Segment s1, Segment s2) { return s1.index == s2.index; }
int main(void)
{
ifstream fin ("cowjump.in");
vector<Segment> S;
vector<Point> P;
fin >> N;
for (int i=0; i<N; i++) {
Segment s;
fin >> s.p.x >> s.p.y >> s.q.x >> s.q.y;
s.index = s.p.segindex = s.q.segindex = i;
S.push_back(s);
P.push_back(s.p); P.push_back(s.q);
}
sort (P.begin(), P.end());
set<Segment> active;
int ans1, ans2; // sweep across scene to locate just one intersecting pair...
for (int i=0; i<N*2; i++) {
ans1 = P[i].segindex; x = P[i].x;
auto it = active.find(S[ans1]);
if (it != active.end()) {
// segment already there -- we've reached its final endpoint. check intersection with the
// pair of segments that becomes adjacent when this one is deleted.
auto after = it, before = it; after++;
if (before != active.begin() && after != active.end()) {
before--;
if (isect(S[before->index], S[after->index]))
{ ans1 = before->index; ans2 = after->index; break; }
}
active.erase(it);
}
else {
// new segment to add to active set.
// check for intersections with only the segments directly above and below (if any)
auto it = active.lower_bound(S[ans1]);
if (it != active.end() && isect(S[it->index], S[ans1])) { ans2 = it->index; break; }
if (it != active.begin()) { it--; if (isect(S[it->index], S[ans1])) { ans2 = it->index; break; } }
active.insert(S[ans1]);
}
}
if (ans1 > ans2) swap (ans1, ans2);
int ans2_count = 0;
for (int i=0; i<N; i++)
if (S[i].index != ans2 && isect(S[i], S[ans2])) ans2_count++;
ofstream fout ("cowjump.out");
fout << (ans2_count > 1 ? ans2+1 : ans1+1) << "\n";
return 0;
}