[C++]백준 - 2162번 문제

2162번: 선분 그룹 (acmicpc.net)

2162번: 선분 그룹

 

2162번 : 선분 그룹

---

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

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

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

 

입력

---

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

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

17387번 문제의 교차 판정을 그대로 이용 + 유니온 파인드로 그룹을 묶어줍니다.

 

그거 말고는 없습니다.

 

코드

---

#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> Point;
#define X first
#define Y second
#define swap(A, B) {Point temp; temp = A; A = B; B = temp;}

#pragma warning (disable : 4996)

//선분 구조체
struct Line
{
    Point P1, P2;

    Line() {}
    Line(ll x1, ll y1, ll x2, ll y2)
    {
        P1.X = x1;
        P1.Y = y1;
        P2.X = x2;
        P2.Y = y2;
    }
};


//CCW 알고리즘
int ccw(Point A, Point B, Point C)
{
    ll temp1 = A.first * B.second + B.first * C.second + C.first * A.second;
    ll temp2 = A.second * B.first + B.second * C.first + C.second * A.first;
    ll result = temp1 - temp2;

    if (result < 0) return -1;
    else if (result == 0) return 0;
    else return 1;
}

//선분 교차 판정
bool is_crossed(Line A, Line B)
{
    Point P1 = A.P1;
    Point P2 = A.P2;
    Point P3 = B.P1;
    Point P4 = B.P2;
    int ccw1 = ccw(P1, P2, P3);
    int ccw2 = ccw(P2, P3, P4);
    int ccw3 = ccw(P3, P4, P1);
    int ccw4 = ccw(P4, P1, P2);

    bool is_crossed;

    //직선일 때
    if (ccw1 * ccw4 == 0 && ccw2 * ccw3 == 0)
    {
        if (P2 < P1) swap(P1, P2);
        if (P4 < P3) swap(P3, P4);

        //겹쳤으면
        if (P1 <= P4 && P3 <= P2) return true;
        else return false;
    }

    return ccw1 * ccw4 <= 0 && ccw2 * ccw3 <= 0;
}

int get_parent(int parents[], int target)
{
    if (parents[target] == target) return target;
    return parents[target] = get_parent(parents, parents[target]);
}

//유니온 파인드 (그룹화)
ll set_union(int parents[], ll count[], int* group_count, int a, int b)
{
    a = get_parent(parents, a);
    b = get_parent(parents, b);

    if (a != b)
    {
        parents[b] = a;
        ll new_count = count[a] + count[b];
        count[a] = new_count;
        count[b] = new_count;
        (*group_count)--;
        return new_count;
    }
    return count[a];
}

int main()
{
    int N;
    scanf("%d", &N);
    
    Line* lines = new Line[N];
    int* parents = new int[N];
    ll* count = new ll[N];
    for (int i = 0; i < N; i++)
    {
        ll x1, x2, y1, y2;
        scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
        lines[i] = Line(x1, y1, x2, y2);
        parents[i] = i;
        count[i] = 1;
    }
    
    ll result = 1;
    int group_count = N;
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            if (is_crossed(lines[i], lines[j]))
            {
                ll returned = set_union(parents, count, &group_count, i, j);
                if (result < returned) result = returned;
            }
        }
    }
    
    printf("%d\n%lld", group_count, result);

    delete[] parents;
    delete[] count;
    delete[] lines;
    return 0;
}

 

그 외

---