USACO 2019 Silver Open #2 Cowjump implementation with Shamos-Hoey algorithm.

cowjump.cpp

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>

typedef struct point {
	long long x, y;
	int num;
	bool lr;

	bool operator< (const struct point &r) const {
		if (y == r.y)
			return x < r.x;
		return y < r.y;
	}
} Point;

typedef struct segment {
	Point s, f;
	int num;

	int ccw (Point p) const {
		long long t = s.x * f.y + f.x * p.y + p.x * s.y - f.x * s.y - p.x * f.y - s.x * p.y;
		if (t < 0) return -1;
		else if (t > 0) return 1;
		return 0;
	}

	bool intersect(const segment seg) const{
		return ccw(seg.s) != ccw(seg.f) && seg.ccw(s) != seg.ccw(f);
	}

	bool operator< (const struct segment &seg) const {
		return s < seg.s;
	}
} Segment;

int n;
Segment line[100005];
Point q[200005];
std::set< Segment > SL;
std::priority_queue< Point, std::vector<Point>, std::greater<Point> > pq;

bool cmpx(const Point &l, const Point &r) {
	if (l.x == r.x)
		return l.y < r.y;
	return l.x < r.x;
}

int main()
{
	freopen("cowjump.in", "r", stdin);
	freopen("cowjump.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		Point s = { x1, y1, i, true }, f = { x2, y2, i, false };
		if (!cmpx(s, f)) {
			Point t = s;
			s = f;
			f = t;
			s.lr = true;
			f.lr = false;
		}
		line[i] = { s, f, i };
		q[i * 2] = s;
		q[i * 2 + 1] = f;
	}
	std::sort(q, q + 2 * n, cmpx);

	int d1 = -1, d2 = -1;
	for (int i = 0; i < 2 * n; i++) {
		Point p = q[i];
		if (p.lr) {		// left
			Segment e = line[p.num];
			SL.insert(e);
			auto segA = SL.upper_bound(e);
			if (segA != SL.end() && e.intersect(*segA) ) {
				d1 = e.num; d2 = segA->num;
				break;
			}
			
			auto segB = SL.lower_bound(e);
			if (segB != SL.begin()) --segB;		// can I use std::prev
			if (segB != SL.end() && e.intersect(*segB)) {
				d1 = e.num; d2 = segB->num;
				break;
			}
		}
		else {			// right
			Segment e = line[p.num];
			auto segA = SL.upper_bound(e);
			auto segB = SL.lower_bound(e);
			if (segB != SL.begin()) --segB;
			SL.erase(e);
			if (segA != SL.end() && segB != SL.end() && (*segA).intersect(*segB)) {
				d1 = segA->num; d2 = segB->num;
				break;
			}
		}
	}

	int c1 = 0, c2 = 0;
	for (int i = 0; i < n; i++) {
		if (i != d1 && line[d1].intersect(line[i])) c1++;
		if (i != d2 && line[d2].intersect(line[i])) c2++;
	}
	if (c1 == c2) {
		printf("%d", std::min(d1, d2) + 1);
	}
	else if (c1 > c2) {
		printf("%d", d1 + 1);
	}
	else {
		printf("%d", d2 + 1);
	}
	return 0;
}