Intersection Points

#include <queue>
#include <vector>
#include <iostream>
#include <unordered_set>

struct SweepEntry {
  SweepEntry(int y_coord, int event, int line_id):
    y_coord(y_coord),
    event(event),
    line_id(line_id)
  {
  }

  int y_coord;
  int event;
  int line_id;
};

struct Line {
  int x1;
  int y1;
  int x2;
  int y2;
};

bool operator< (SweepEntry const &lhs, SweepEntry const &rhs) {
  if (lhs.y_coord == rhs.y_coord) {
    return lhs.event < rhs.event;
  }

  return lhs.y_coord < rhs.y_coord;
}

bool operator> (SweepEntry const &lhs, SweepEntry const &rhs) {
  if (lhs.y_coord == rhs.y_coord) {
    return lhs.event > rhs.event;
  }

  return lhs.y_coord > rhs.y_coord;
}

struct Point {
  Point (int x, int y) :
    x(x),
    y(y)
  {
  }

  int x;
  int y;
};

bool ccw(Point const &A, Point const &B, Point const &C) {
  return ((C.y - A.y) * (B.x - A.x)) > ((B.y - A.y) * (C.x - A.x));
}

bool intersects(Line const &lhs, Line const &rhs) {
  Point A(lhs.x1, lhs.y1);
  Point B(lhs.x2, lhs.y2);
  Point C(rhs.x1, rhs.y1);
  Point D(rhs.x2, rhs.y2);

  return (
    (ccw(A, C, D) != ccw(B, C, D)) && (ccw(A, B, C) != ccw(A, B, D))
  );
}

int main(void) {
  int n;

  std::cin >> n;
  std::vector<Line> lines(n);

  for (int i = 0; i < n; ++i) {
    std::cin >> lines[i].x1;
    std::cin >> lines[i].y1;
    std::cin >> lines[i].x2;
    std::cin >> lines[i].y2;
  }

  std::priority_queue<SweepEntry, std::vector<SweepEntry>, std::greater <SweepEntry>> q;
  std::unordered_set<int> active;

  int intersections = 0;

  for (int i = 0; i < n; ++i) {
    q.push(SweepEntry(lines[i].y1, 1, i));
    q.push(SweepEntry(lines[i].y2, 2, i));
  }

  while (!q.empty()) {
    SweepEntry e = q.top();
    q.pop();

    // Compare it to the other active lines
    if (e.event == 1) {

      for (auto line : active) {
        if (intersects(lines[e.line_id], lines[line])) {
          ++intersections;
        }
      }

      active.insert(e.line_id);
    } else if (e.event == 2) {
      active.erase(e.line_id);
    }
  }

  std::cout << intersections << std::endl;

  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: UNKNOWN