선분 그룹

Problme link: https://www.acmicpc.net/problem/2162

문제가 어렵다기 보다는 자료구조를 여러개 써줘야한다.

• CCW를 활용한 선분 교차여부 판단을 위해서 벡터, 라인 자료구조를 사용하였고,
• 그루핑을 위해 서로소 집합을 사용하였다.

CCW를 활용하는 교차여부 판단 시 둘 다 0인 경우에만 예외처리가 필요함을 잘 기억해두도록하자.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdint>

using namespace std;

int N;

class Vector
{
public:
  int64_t x, y;

  Vector()
  {
  }
  Vector(const int64_t x, const int64_t y) : x(x), y(y)
  {
  }

  int64_t operator*(const Vector& rhs) const
  {
    return x * rhs.y - y * rhs.x;
  }

  Vector operator-(const Vector& rhs) const
  {
    return Vector(x - rhs.x, y - rhs.y);
  }

  bool operator<(const Vector& rhs) const
  {
    if (x != rhs.x)
    {
      return x < rhs.x;
    }

    return y < rhs.y;
  }
};

class Line
{
public:
  Vector start, end;

  Line()
  {
  }
  Line(const Vector& start, const Vector& end) : start(start), end(end)
  {
    if (end < start)
    {
      swap<Vector>(this->start, this->end);
    }
  }
};

bool HasIntersect(const Line& l1, const Line& l2)
{
  int64_t l1_l2 = ((l1.end - l1.start) * (l2.start - l1.end)) * ((l1.end - l1.start) * (l2.end - l1.end));
  int64_t l2_l1 = ((l2.end - l2.start) * (l1.start - l2.end)) * ((l2.end - l2.start) * (l1.end - l2.end));

  if (l1_l2 == 0 && l2_l1 == 0)
  {
    return !(l1.end < l2.start || l2.end < l1.start);
  }

  return l1_l2 <= 0 && l2_l1 <= 0;
}

class Set
{
public:
  vector<int> parent;
  vector<int> number_of_elem;
  Set(const int size) : parent(size, -1), number_of_elem(size, 1)
  {
  }
  int Find(const int idx)
  {
    if (parent[idx] != -1)
    {
      parent[idx] = Find(parent[idx]);
      return parent[idx];
    }
    return idx;
  }
  void Union(const int a, const int b)
  {
    int root_a = Find(a);
    int root_b = Find(b);
    if (root_a == root_b)
    {
      return;
    }
    parent[root_a] = root_b;
    number_of_elem[root_b] += number_of_elem[root_a];
  }
};

void Solve(const vector<Line>& lines)
{
  Set dset(N);

  for (int i = 0; i < N; ++i)
  {
    for (int j = i + 1; j < N; ++j)
    {
      if (HasIntersect(lines[i], lines[j]))
      {
        dset.Union(i, j);
      }
    }
  }

  int number_of_group = 0;
  int max_group_size = -1;

  for (int i = 0; i < N; ++i)
  {
    if (dset.parent[i] == -1)
    {
      ++number_of_group;
      max_group_size = max(max_group_size, dset.number_of_elem[i]);
    }
  }

  printf("%d\n%d\n", number_of_group, max_group_size);
}

int main(void)
{
  // Read input
  scanf(" %d", &N);
  vector<Line> lines;
  for (int it = 0; it < N; ++it)
  {
    Vector start, end;
    scanf(" %ld %ld %ld %ld", &start.x, &start.y, &end.x, &end.y);
    lines.emplace_back(start, end);
  }

  // Solve
  Solve(lines);

  return 0;
}