b2162. 선분그룹

 

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

 

 

 

 선분 교차 여부를 판별해 선분 그룹을 나누고,
각 그룹의 크기와 전체 그룹의 개수를 계산하여 풀이했다.
입력으로 주어진 선분들을 Line 객체로 저장하고,
Union-Find 자료구조를 사용해 선분 교차 관계를 기반으로 그룹을 형성한다.
각 선분은 시작점과 끝점을 Dot 객체로 표현하며,
시작점이 항상 더 작은 값을 가지도록 정렬하여 일관성을 유지한다.

두 선분의 교차 여부는 isCross 메서드를 통해 확인하며,
CCW 메서드를 사용해 세 점이 반시계 방향,
시계 방향, 또는 일직선상에 있는지를 판별한다.
교차하는 경우 Union-Find의 union 메서드를 통해 두 선분을 같은 그룹으로 합친다.
그룹은 size 배열을 통해 크기를 관리하며,
경로 압축을 활용해 효율적으로 처리된다.

모든 교차 판별이 끝난 후,
각 선분의 루트를 찾아 그룹의 개수를 계산하고,
그룹 크기의 최댓값을 갱신한다.
결과적으로 그룹의 수와 최대 그룹 크기를 출력해 풀이했다.

문제를 풀이하는 과정에서 선분 교차검증 방법
CCW를 몰라 GPT에게 물어보고 
CCW의 원리를 몰라 GPT에게 물어보고

스위핑 라인 알고리즘을 활용하여 문제를 풀이하라는 추천이 있어서
스위핑 라인 알고리즘을 활용해 선분 교차검증을 하고 unionfind 하였지만
여러 오류가 발생했고 시간적으로 너무 오래걸려

결국 CCW+ 완전탐색+ union-find 알고리즘 활용하여 풀이하였다.

벡터와 외적, CCW 알고리즘, 스위핑라인 알고리즘, UnionFind by Size에
여러 지식을 얻을 수 있었지만 풀이과정이 너무나도 험난하고 오래걸렸다.

CCW 공식을 이해하기위해서 벡터, 외적에 관한 수학적 이론지식이 필요하다
(b.x−a.x),(b.y−a.y)
이건 AB 벡터값이고
(c.x−a.x),(c.y−a.y)
이건 AC 벡터값인것

CCW 는 이를 AB 벡터에서 AC벡터로 갈려면 시계방향으로가야하는지
반시계방향으로가야하는지 
기울기가 같은 일직선인지 알수 있는 공식이며 이는

(b.x−a.x)(c.y-a.y)-(b.y−a.y)(c.x-a.x)
이렇게 나타낸다는것

이값이 양수면 반시계
음수면 시계
0이면 일직선 이라는것을 배웠다.

일직선이게되면 이 일직선인 AB벡터와 AC벡터가 과연 겹치는지 안겹치는지를 
Min(a.x,b.x) <= Max(c.x,d.x) &&
Min(a.y,b.y) <= Max(c.y,d.y) &&

Min(c.x,d.x) <= Max(a.x,b.x) &&

Min(c.y,d.y) <= Max(a.y,b.y)
이 네가지를 모두 만족하면 겹친다는것 또한 배웠다.

Union By Size를 활용하여 UnionFind의 경로압축에 더하여 
사이즈 기준으로 큰쪽으로 Union 하여 보다 시간복잡도를 개선하는방법도 배웠다.

 

 

 

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

public class Main {
    static int N;
    static int[] parent, size;

    static class Dot {
        int x, y;

        public Dot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Line {
        Dot start, end;

        public Line(Dot start, Dot end) {
            if (start.x > end.x || (start.x == end.x && start.y > end.y)) {
                Dot temp = start;
                start = end;
                end = temp;
            }
            this.start = start;
            this.end = end;
        }
    }

    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            if (size[rootA] < size[rootB]) {
                parent[rootA] = rootB;
                size[rootB] += size[rootA];
            } else {
                parent[rootB] = rootA;
                size[rootA] += size[rootB];
            }
        }
    }

    static int ccw(Dot a, Dot b, Dot c) {
        long value = (long) (b.x - a.x) * (c.y - a.y) - (long) (b.y - a.y) * (c.x - a.x);
        return Long.compare(value, 0);
    }

    static boolean isCross(Line l1, Line l2) {
        Dot a = l1.start, b = l1.end;
        Dot c = l2.start, d = l2.end;
        int ccw1 = ccw(a, b, c) * ccw(a, b, d);
        int ccw2 = ccw(c, d, a) * ccw(c, d, b);

        if (ccw1 == 0 && ccw2 == 0) {
            return Math.min(a.x, b.x) <= Math.max(c.x, d.x) && Math.min(c.x, d.x) <= Math.max(a.x, b.x) &&
                    Math.min(a.y, b.y) <= Math.max(c.y, d.y) && Math.min(c.y, d.y) <= Math.max(a.y, b.y);
        }
        return ccw1 <= 0 && ccw2 <= 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        Line[] lines = new Line[N];
        parent = new int[N];
        size = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            lines[i] = new Line(new Dot(x1, y1), new Dot(x2, y2));
        }

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (isCross(lines[i], lines[j])) {
                    union(i, j);
                }
            }
        }

        int groupCount = 0;
        int maxSize = 0;
        for (int i = 0; i < N; i++) {
            if (find(i) == i) groupCount++;
            maxSize = Math.max(maxSize, size[find(i)]);
        }

        System.out.println(groupCount);
        System.out.println(maxSize);
    }
}