[백준(Baekjoon)][자바(java)] 2162 : 선분 그룹 / 기하

 

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

2162번: 선분 그룹

 

문제 풀이

 

 ▷  CCW  +  Union-Find

import java.io.*;
import java.util.*;

public class Main {
	
	static int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { // CounterClockWise
		long value = (long) (x2 - x1) * (y3 - y1) - (long) (x3 - x1) * (y2 - y1);
		return value < 0 ? -1 : value > 0 ? 1 : 0; // -1 : 시계 방향, 1 : 반시계 방향, 0 : 일직선
	}

	static boolean isIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
		int d123 = ccw(x1, y1, x2, y2, x3, y3), d124 = ccw(x1, y1, x2, y2, x4, y4),
			d341 = ccw(x3, y3, x4, y4, x1, y1), d342 = ccw(x3, y3, x4, y4, x2, y2);
		int v12 = d123 * d124, v34 = d341 * d342;
		if (v12 == 0 && v34 == 0) {
			if (d123 == 0 && d124 == 0 && d341 == 0 && d342 == 0) { // 네 점이 일직선
				int pA, pB, pC, pD;
				if (x1 == x2)	{ pA = Math.min(y1, y2); pB = Math.max(y1, y2); }
				else 			{ pA = Math.min(x1, x2); pB = Math.max(x1, x2); }
				if (x3 == x4)	{ pC = Math.min(y3, y4); pD = Math.max(y3, y4); }
				else 			{ pC = Math.min(x3, x4); pD = Math.max(x3, x4); }
				return pC <= pB && pA <= pD; // 두 선분이 만나거나 겹침
			}
			return true; // 세 점이 일직선인데 그 중 두 점이 겹침
		}
		return v12 <= 0 && v34 <= 0; // 세 점이 일직선인데 두 점 사이에 있거나 / 두 선분이 서로 교차
	}

	static int find(int x, int p[]) { // 경로 압축
		return x == p[x] ? x : (p[x] = find(p[x], p));
	}

	static void union(int a, int b, int p[], int r[]) { // 랭크 이용
		a = find(a, p);
		b = find(b, p);
		if (r[a] > r[b])
			p[b] = a;
		else {
			p[a] = b;
			if (r[a] == r[b]) r[b]++;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int point[][] = new int[n][4], i, j;
		for (i = 0; i < n; ++i) {
			st = new StringTokenizer(br.readLine());
			for (j = 0; j < 4; ++j)
				point[i][j] = Integer.parseInt(st.nextToken());
		}
		br.close();
		int parent[] = new int[n], rank[] = new int[n], x1, y1, x2, y2;
		for (i = 0; i < n; i++ )
			parent[i] = i;
		for (i = 0; i < n - 1; ++i) {
			x1 = point[i][0]; y1 = point[i][1];
			x2 = point[i][2]; y2 = point[i][3];
			for (j = i + 1; j < n; ++j)
				if (isIntersect(x1, y1, x2, y2, point[j][0], point[j][1], point[j][2], point[j][3]))
					union(i, j, parent, rank);
		}
		for (i = 0; i < n; i++ )
			parent[i] = find(i, parent);
		TreeMap<Integer, Integer> tm = new TreeMap<>();
		for (int p : parent)
			tm.put(p, tm.getOrDefault(p, 0) + 1);
		int max = 0;
		for (int val : tm.values())
			if (max < val)
				max = val;
		System.out.println(tm.size() + "\n" + max);
	} 
}