[BOJ] 2162: 선분 그룹 (C/C++)

문제 2162번: 선분 그룹

N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.

두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.

N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자.

입력

첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다.

출력

첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한 선분의 개수를 출력한다.

문제분석

문제 요구사항

• 선분이 서로 곂치는지 판별해야 한다. -> CCW(Counter Clock Wise) 알고리즘을 활용하여 해결한다.
• 서로 곂치는 직선을 한 개의 그룹으로 판별해야 한다. -> Disjoint Set 알고리즘을 활용하여 해결한다.

CCW와 Disjoint Set을 이용하여 구현한다.

구현

CCW를 활용하여 두 직선이 교차하는지 검사한 후, 만약 두 직선이 교차 한다면, 두 직선의 Set을 Merge한 후, 총 집합의 갯수와, 집합중 최대 크기 집합의 집합 크기를 출력한다.

증명

CCW 알고리즘은 외적을 이용하여 점 3개의 직선방향을 알고자 할때 유용한 알고리즘이다. 따라서 CCW 알고리즘을 응용하면 두 직선이 서로 교차하는지 확인 할 수 있다.
따라서 두 직선이 교차한다하면 Disjoint Set을 이용하여 두 Set을 Merge 하여 구현한다.

코드

#include <iostream>
#include <utility>
#include <vector>

int cnt_sets;
int max_set_size = 1;
std::vector<int> sets;
std::vector<int> sets_size;

const int GetSet(const int set) {
  if (sets[set] == set) {
    return set;
  }
  return sets[set] = GetSet(sets[set]);
}

void MergeSet(int lset, int rset) {
  lset = GetSet(lset);
  rset = GetSet(rset);
  if (lset == rset) {
    return;
  }

  if (rset < lset) {
    std::swap(rset, lset);
  }

  sets[rset] = lset;
  sets_size[lset] += sets_size[rset];

  --cnt_sets;

  return;
}

std::istream& operator>>(std::istream& is, std::pair<int, int>& p) {
  is >> p.first >> p.second;
  return is;
}
/*CCW only return 1, 0, -1*/
const int CCW(const std::pair<int, int>& p0, const std::pair<int, int>& p1,
              const std::pair<int, int>& p2) {
  const int calc_0 =
      p0.first * p1.second + p1.first * p2.second + p2.first * p0.second;
  const int calc_1 =
      p1.first * p0.second + p2.first * p1.second + p0.first * p2.second;
  return calc_0 == calc_1 ? 0 : calc_0 > calc_1 ? 1 : -1;
}

struct Line {
  std::pair<int, int> p0;
  std::pair<int, int> p1;

  const bool Intersect(const Line& l) const {
    const int this_line =
        CCW(this->p0, this->p1, l.p0) * CCW(this->p0, this->p1, l.p1);
    if (this_line > 0) {
      return false;
    }

    const int other_line =
        CCW(l.p0, l.p1, this->p0) * CCW(l.p0, l.p1, this->p1);
    if (other_line > 0) {
      return false;
    }

    return this_line == 0 && other_line == 0
               ? l.p0 <= this->p1 && this->p0 <= l.p1
               : true;
  }
};

std::istream& operator>>(std::istream& is, Line& l) {
  is >> l.p0 >> l.p1;
  return is;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);

  int N;
  std::cin >> N;

  cnt_sets = N;

  sets.assign(cnt_sets, 0);
  for (int i = 0; i < sets.size(); ++i) {
    sets[i] = i;
  }
  sets_size.assign(cnt_sets, 1);

  std::vector<Line> lines(N);
  for (int i = 0; i < lines.size(); ++i) {
    std::cin >> lines[i];

    if (lines[i].p0 > lines[i].p1) {
      std::swap(lines[i].p0, lines[i].p1);
    }

    for (int j = 0; j < i; ++j) {
      if (lines[i].Intersect(lines[j])) {
        MergeSet(i, j);
      }
    }
  }

  for (int i = 0; i < sets_size.size(); ++i) {
    max_set_size = std::max(max_set_size, sets_size[i]);
  }

  std::cout << cnt_sets << "\n" << max_set_size;

  return 0;
}