cgl_6_a aoj 線分の交差 マンハッタン幾何

CGL_6_A | 線分の交差(マンハッタン幾何)

CGL_6_A | 線分の交差(マンハッタン幾何)
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_6_A

水平あるいは垂直な線分が複数与えられてそれらの交点の総数をもとめる問題.

解説

アルゴリズムについての詳細は以下を参照.

線分交差 | ラインスウィープアルゴリズム

計算量

$$
O(N \log N)
$$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
Int N;
vector<Point> points;
Point p1, p2;
set<Int> BT;

Int line_sweep() {
  Int count = 0;
  sort(span_all(points));

  for (auto p: points) {
    switch (p.type) {
      case DOWN:
        BT.insert(p.coord.x);
        break;
      case LEFT:
        count += distance(
          lower_bound(span_all(BT), p.coord.x),
          upper_bound(span_all(BT), p.coord.x + p.length)
        );
        break;
      case UP:
        BT.erase(p.coord.x);
        break;
      case RIGHT:
        // do nothing
        break;
    }
  }
  return count;
}

void solve() {
  cout << line_sweep() << endl;
}

void input() {
  cin >> N;
  loop(n,0,N) {
    cin >> p1.coord >> p2.coord;
    if (p1.coord.y == p2.coord.y) {
      if (p1.coord.x < p2.coord.x) p1.type = LEFT,p2.type = RIGHT;
      else p1.type = RIGHT,p2.type = LEFT;
      p1.length = p2.length = fabs(p1.coord.x - p2.coord.x);
    } else {
      if (p1.coord.y < p2.coord.y) p1.type = DOWN,p2.type = UP;
      else p1.type = UP,p2.type = DOWN;
      p1.length = p2.length = fabs(p1.coord.y - p2.coord.y);
    }
    points.push_back(p1), points.push_back(p2);
  }
}

int main() {
  input();
  solve();
}