Line Intersections

#include <bits/stdc++.h>
using namespace std;

#define I_2D(row, col, width) ((row) * (width) + (col))
#define PRINT_ARR(arr, n)                                                      \
  do {                                                                         \
    for (int i = 0; i < n; i++) {                                              \
      cout << arr[i] << " ";                                                   \
    }                                                                          \
    cout << "\n";                                                              \
  } while (0)
#define PRINT_VEC_ARR(v, n)                                                    \
  do {                                                                         \
    for (int i = 0; i < n; i++) {                                              \
      cout << i << ": ";                                                       \
      for (auto item : v[i]) {                                                 \
        cout << item << " ";                                                   \
      }                                                                        \
      cout << endl;                                                            \
    }                                                                          \
  } while (0)
#define endl '\n';

typedef long long ll;
typedef complex<ll> pp;
typedef pair<pair<ll, ll>, ll> tr;

#define maxX ((int)1e6 + 5)
#define SIZE (2 * maxX)
ll bin_ind_tr[SIZE];

ll bi_sum(int k) {
  int s = 0;
  k += maxX;
  while (k > 0) {
    s += bin_ind_tr[k];
    k = (k & (k + 1)) - 1;
  }
  return s;
}

void bi_add(int k, int value) {
  k += maxX;
  while (k < SIZE) {
    bin_ind_tr[k] += value;
    k = k | (k + 1);
  }
}


enum events_t {
  HORIZONTAL_START = 0,
  VERTICAL = 1,
  HORIZONTAL_END = 2,
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;

  vector<vector<ll>> lines(n, vector<ll>(4));

  for (int i = 0; i < n; i++) {
    cin >> lines[i][0] >> lines[i][1] >> lines[i][2] >> lines[i][3];
  }

  // calculate
  vector<vector<ll>> events;

  ll tmp;
  for (auto line : lines) {
    ll x1 = line[0], y1 = line[1], x2 = line[2], y2 = line[3];
    if (x1 == x2) {
      // vertical
      if (y1 > y2) {
        tmp = y1;
        y1 = y2;
        y2 = tmp;
      }
      events.push_back({x1, VERTICAL, y1, y2});
    } else {
      // horizontal
      if (x1 > x2) {
        tmp = x1;
        x1 = x2;
        x2 = tmp;
      }
      events.push_back({x1, HORIZONTAL_START, y1});
      events.push_back({x2, HORIZONTAL_END, y1});
    }
  }

  sort(events.begin(), events.end());

  ll intersections = 0;
  set<ll> ys;
  for (auto e : events) {
    if (e[1] == VERTICAL) {
      // TODO:
      intersections += bi_sum(e[3]) - bi_sum(e[2]-1);
    } else if (e[1] == HORIZONTAL_START) {
      // ys.insert(e[2]);
      bi_add(e[2], 1);
    } else {
      bi_add(e[2], -1);
    }
  }
  cout << intersections << endl;

  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: WRONG ANSWER

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: WRONG ANSWER

Test 39

Verdict: WRONG ANSWER

Test 40

Verdict: WRONG ANSWER