[BOJ] 2162 - 선분 그룹

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

BOJ - 선분 그룹

문제 유형: CCW, 선형대수, 기하학, 유니온-파인드, 분리 집합

문제 난이도: Platinum V

시간 제한: 2초

메모리 제한: 128MB

 

문제

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

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

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

 

입력

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

 

출력

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

 

풀이

CCW에 대한 이해는 여기서:

https://riveroverflow.tistory.com/entry/BOJ-17387-%EC%84%A0%EB%B6%84-%EA%B5%90%EC%B0%A8-2

[BOJ] 17387 - 선분 교차 2

 

 

CCW를 통해서 선분들 간의 교차관계를 구한다.

ccw1 = ccw(선분i의 두 점, 선분 j의 점 1)

ccw2 = ccw(선분i의 두 점, 선분 j의 점 2)

ccw3 = ccw(선분j의 두 점, 선분 i의 점 1)

ccw4 = ccw(선분j의 두 점, 선분 i의 점 2)

를 구한다.

ccw1 * ccw2 < 0 && ccw3 * ccw4가 음수라면 엄밀히 교차한다.

ccw1 == 0이고, 선분j의 점 1이 선분 i위에 있다면, 같은 기울기의 선분 i, j가 이어져있는 형태이다.

ccw2 == 0이고, 선분j의 점 2가 선분 i위에 있다면, 같은 기울기의 선분 i, j가 이어져있는 형태이다.

ccw3 == 0이고, 선분i의 점 1이 선분 j위에 있다면, 같은 기울기의 선분 i, j가 이어져있는 형태이다.

ccw4 == 0이고, 선분i의 점 2가 선분 j위에 있다면, 같은 기울기의 선분 i, j가 이어져있는 형태이다.

 

교차한다면 유니온파인드로 합치고, 병합에 성공 시 요소의 개수까지 합친다.

최종적으로 parent[i]가 i인, 즉 루트들에 대해서 분리집합의 개수와 최대 크기를 갱신해주고, 출력한다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>

using namespace std;

struct Line {
  int x1;
  int y1;
  int x2;
  int y2;
  Line(int x1, int y1, int x2, int y2) {
    this->x1 = x1;
    this->y1 = y1;
    this->x2 = x2;
    this->y2 = y2;
  }
};

int ccw(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
  ll res = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
  if (res > 0)
    return 1;
  if (res < 0)
    return -1;
  return 0;
}

bool isPoint(int x, int y, int x1, int y1, int x2, int y2) {
  return x >= min(x1, x2) && x <= max(x1, x2) && y >= min(y1, y2) &&
         y <= max(y1, y2);
}

bool isIntersect(int i, int j, vector<Line *> &lines) {
  int ccw1 = ccw(lines[i]->x1, lines[i]->y1, lines[i]->x2, lines[i]->y2,
                 lines[j]->x1, lines[j]->y1);
  int ccw2 = ccw(lines[i]->x1, lines[i]->y1, lines[i]->x2, lines[i]->y2,
                 lines[j]->x2, lines[j]->y2);
  int ccw3 = ccw(lines[j]->x1, lines[j]->y1, lines[j]->x2, lines[j]->y2,
                 lines[i]->x1, lines[i]->y1);
  int ccw4 = ccw(lines[j]->x1, lines[j]->y1, lines[j]->x2, lines[j]->y2,
                 lines[i]->x2, lines[i]->y2);

  if (ccw1 * ccw2 < 0 && ccw3 * ccw4 < 0)
    return true;

  if (ccw1 == 0 && isPoint(lines[j]->x1, lines[j]->y1, lines[i]->x1,
                           lines[i]->y1, lines[i]->x2, lines[i]->y2))
    return true;
  if (ccw2 == 0 && isPoint(lines[j]->x2, lines[j]->y2, lines[i]->x1,
                           lines[i]->y1, lines[i]->x2, lines[i]->y2))
    return true;
  if (ccw3 == 0 && isPoint(lines[i]->x1, lines[i]->y1, lines[j]->x1,
                           lines[j]->y1, lines[j]->x2, lines[j]->y2))
    return true;
  if (ccw4 == 0 && isPoint(lines[i]->x2, lines[i]->y2, lines[j]->x1,
                           lines[j]->y1, lines[j]->x2, lines[j]->y2))
    return true;
  return false;
}

int getRoot(int x, vector<int> &parent) {
  if (parent[x] == x)
    return x;
  return parent[x] = getRoot(parent[x], parent);
}

void merge(int u, int v, vector<int> &parent, vector<int> &componentSize) {
  int uRoot = getRoot(u, parent);
  int vRoot = getRoot(v, parent);

  if (uRoot == vRoot)
    return;

  if (uRoot < vRoot) {
    parent[vRoot] = uRoot;
    componentSize[uRoot] += componentSize[vRoot];
  } else {
    parent[uRoot] = vRoot;
    componentSize[vRoot] += componentSize[uRoot];
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;

  vector<Line *> lines(n);
  vector<int> parent(n);
  vector<int> componentSize(n, 1);
  for (int i = 0; i < n; ++i) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    lines[i] = new Line(x1, y1, x2, y2);
    parent[i] = i;
  }

  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (isIntersect(i, j, lines)) {
        merge(i, j, parent, componentSize);
      }
    }
  }

  int count = 0;
  int maxSize = 0;
  for (int i = 0; i < n; ++i) {
    if (parent[i] == i) {
      count++;
      maxSize = max(maxSize, componentSize[i]);
    }
  }

  cout << count << "\n" << maxSize << "\n";

  return 0;
}

 

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

var reader *bufio.Reader
var writer *bufio.Writer

type Line struct {
	x1 int64
	y1 int64
	x2 int64
	y2 int64
}

func min(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func ccw(x1, y1, x2, y2, x3, y3 int64) int64 {
	x := (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)
	if x > 0 {
		return 1
	} else if x < 0 {
		return -1
	} else {
		return 0
	}
}

func isIntersect(i, j int64, lines []Line) bool {
	ccw1 := ccw(lines[i].x1, lines[i].y1, lines[i].x2, lines[i].y2, lines[j].x1, lines[j].y1)
	ccw2 := ccw(lines[i].x1, lines[i].y1, lines[i].x2, lines[i].y2, lines[j].x2, lines[j].y2)
	ccw3 := ccw(lines[j].x1, lines[j].y1, lines[j].x2, lines[j].y2, lines[i].x1, lines[i].y1)
	ccw4 := ccw(lines[j].x1, lines[j].y1, lines[j].x2, lines[j].y2, lines[i].x2, lines[i].y2)

	if ccw1*ccw2 < 0 && ccw3*ccw4 < 0 {
		return true
	}
	if ccw1 == 0 &&
		lines[j].x1 >= min(lines[i].x1, lines[i].x2) && lines[j].x1 <= max(lines[i].x1, lines[i].x2) &&
		lines[j].y1 >= min(lines[i].y1, lines[i].y2) && lines[j].y1 <= max(lines[i].y1, lines[i].y2) {
		return true
	}
	if ccw2 == 0 &&
		lines[j].x2 >= min(lines[i].x1, lines[i].x2) && lines[j].x2 <= max(lines[i].x1, lines[i].x2) &&
		lines[j].y2 >= min(lines[i].y1, lines[i].y2) && lines[j].y2 <= max(lines[i].y1, lines[i].y2) {
		return true
	}
	if ccw3 == 0 &&
		lines[i].x1 >= min(lines[j].x1, lines[j].x2) && lines[i].x1 <= max(lines[j].x1, lines[j].x2) &&
		lines[i].y1 >= min(lines[j].y1, lines[j].y2) && lines[i].y1 <= max(lines[j].y1, lines[j].y2) {
		return true
	}
	if ccw4 == 0 &&
		lines[i].x2 >= min(lines[j].x1, lines[j].x2) && lines[i].x2 <= max(lines[j].x1, lines[j].x2) &&
		lines[i].y2 >= min(lines[j].y1, lines[j].y2) && lines[i].y2 <= max(lines[j].y1, lines[j].y2) {
		return true
	}

	return false
}

func getRoot(x int64, parent []int64) int64 {
	if parent[x] == x {
		return x
	}
	parent[x] = getRoot(parent[x], parent)
	return parent[x]
}

func merge(u, v int64, parent, componentSizes []int64) {
	uRoot := getRoot(u, parent)
	vRoot := getRoot(v, parent)

	if uRoot == vRoot {
		return
	}

	if uRoot < vRoot {
		componentSizes[uRoot] += componentSizes[vRoot]
		parent[vRoot] = uRoot
	} else {
		componentSizes[vRoot] += componentSizes[uRoot]
		parent[uRoot] = vRoot
	}
}

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int64
	fmt.Fscan(reader, &n)
	var x1, y1, x2, y2 int64
	lines := make([]Line, n)
	parent := make([]int64, n)
	componentSizes := make([]int64, n)

	for i := int64(0); i < n; i++ {
		fmt.Fscan(reader, &x1, &y1, &x2, &y2)
		lines[i] = Line{x1, y1, x2, y2}
		parent[i] = i
		componentSizes[i] = 1
	}

	for i := int64(0); i < n; i++ {
		for j := i + 1; j < n; j++ {
			if isIntersect(i, j, lines) {
				merge(i, j, parent, componentSizes)
			}
		}
	}

	count := int64(0)
	maxSize := int64(0)
	for i := int64(0); i < n; i++ {
		if parent[i] == i {
			count++
			if componentSizes[i] > maxSize {
				maxSize = componentSizes[i]
			}
		}
	}

	fmt.Fprintln(writer, count)
	fmt.Fprintln(writer, maxSize)
}