Line Intersections

#include <iostream>
#include <cmath>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
#define rep(i, a, b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;

constexpr double PI = 3.14159265358979323846;

/**
 * Author: Ulf Lundstrom
 * Date: 2009-02-26
 * License: CC0
 * Source: My head with inspiration from tinyKACTL
 * Description: Class to handle points in the plane.
 * 	T can be e.g. double or long long. (Avoid int.)
 * Status: Works fine, used a lot
 */
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
  friend istream& operator>>(istream& os, P& p) {
		return os >> p.x >> p.y; }
	friend ostream& operator<<(ostream& os, P p) {
		return os << '(' << p.x << ',' << p.y << ')'; }
};
typedef Point<int> pd;

using seg_type = int;
#define SE_OP(a, b) a + b

const int N = 1<<21;

seg_type S[N*2];

void init() {
  rep(i,0,N*2) S[i] = 0;
}

void add(int i, seg_type x) {
  i |= N;
  S[i] = x;
  for (i /= 2; i >= 1; i /= 2) {
    S[i] = SE_OP(S[i*2], S[i*2+1]);
  }
}

seg_type get(int a, int b) {
  a |= N; b |= N;
  seg_type s = 0;
  while (a <= b) {
    if (a % 2 == 1) {
      s = SE_OP(s, S[a]);
      ++a;
    } if (b % 2 == 0) {
      s = SE_OP(s, S[b]);
      --b;
    }
    a /= 2; b /= 2;
  }
  return s;
}

int main() {
  const int S = 1e6;
  int n;
  cin >> n;
  vector<tuple<int,int,int,int>> P;
  rep(i,0,n) {
    pd p1, p2;
    cin >> p1 >> p2;
    p1.x += S; p1.y += S;
    p2.x += S; p2.y += S;
    if (p1.x == p2.x) {
      if (p1.y > p2.y) swap(p1,p2);
      P.push_back({p1.x,2,p1.y,p2.y});
    } else {
      assert(p1.y == p2.y);
      if (p1.x > p2.x) swap(p1,p2);
      P.push_back({p1.x,1,p1.y,0});
      P.push_back({p2.x,3,p1.y,0});
    }
  }
  sort(all(P));
  ll ans = 0;
  for (auto [x,e,y1,y2] : P) {
    if (e == 2) ans += get(y1,y2);
    else add(y1,e == 1 ? 1 : 0);
  }
  cout << ans << '\n';
}

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