선분 교차 판정 알고리즘 문제 풀이 정리 220828

백준 BOJ 20149번 : 선분 교차 3

문제 난이도 : Platinum IV

알고리즘 분류 : 기하학, 선분 교차 판정

 

두 선분의 끝 점의 좌표가 주어질 때, 두 선분의 교차 여부를 구하고, 만약 한 점에서만 교차한다면 그 좌표를 오차 범위 1e-9 이내로 구하는 문제이다.

 

CCW 값들을 가지고 잘 푸는 것인지는 당연히 아는데, 케이스를 어떻게 나눠야 깔끔하게 정리되는지 도저히 구상이 안 되어서 다른 블로그를 보고 공부했다.

개인적으로는 이 링크에 설명이 가장 잘 되어있다고 생각하고 또 여기서 대부분의 코드를 참고했다. (20220829 수정 : 링크가 잘못 걸려 있었다;;)

 

일단 교차 판정을 먼저 해보자. 점은 a, b, c, d의 네 점이 주어지고 a, b를 잇는 선분과 c, d를 잇는 선분이 있다고 하자.

ccw 값을 이용하면 세 점의 방향 배치를 알 수 있다. (ccw > 0이면 세 점이 시계 반대 방향, ccw < 0이면 시계 방향, ccw = 0이면 세 점은 일직선 상에 있다.)

 

ccw(a, b, c) x ccw(a, b, d) 값과 ccw(c, d, a) x ccw(c, d, b) 값이 둘 다 0이라면 두 선분은 평행이거나 끝 점이 일치하는 경우이다.

a와 b, 그리고 c와 d를 좌표가 증가하게 정렬을 일단 해준 다음에 생각해보자.

(1) a ≤ d인데 b ≥ c라면 ab의 오른쪽 끝과 cd의 왼쪽 끝이 겹친다는 뜻이다.

(2) 그게 아니라면 두 점은 교차하지 않는다.

 

ccw(a, b, c) x ccw(a, b, d) 값과 ccw(c, d, a) x ccw(c, d, b) 값 중 하나라도 0이 아니라면 다음과 같이 나눌 수 있다.

(1) 두 값이 모두 0 이하라면 두 선분은 가운데가 교차하거나, 또는 한 선분의 끝점이 다른 선분의 가운데에 위치하는 경우이다.

(2) 그게 아니라면 두 선분은 교차하지 않는다.

 

이제 두 선분이 교차하는 경우에 한해 좌표를 구해주어야 하는데, 수학 문제를 손으로 푸는게 아닌 수식을 코드로 작성할 것이기 때문에 다음의 공식을 사용하는 것이 가장 편하다. (식이 길더라도 변수를 많이 안 쓰고 처리하는 편이 수월하다는 이야기)

(교점의 좌표) = (((x1y2 - y1x2)(x3 - x4) - (x1 - x2)(x3y4 - y3x4)) / ((x1 - x2)(y3 - y4) - (y1 - y2)(x3 - x4)), ((x1y2 - y1x2)(y3 - y4) - (y1 - y2)(x3y4 - y3x4)) / ((x1 - x2)(y3 - y4) - (y1 - y2)(x3 - x4)))

 

문제는 분모가 0인 경우인데, 이 경우에는 다음의 두 경우로 나뉜다.

(1) b = c이고 a ≤ c이면 : 점 b = c에서 교차하는 것이므로 b의 좌표나 c의 좌표 둘 중 하나를 출력해주면 된다.

(2) a = d이고 c ≥ a이면 : 점 a = d에서 교차하는 것이므로 a의 좌표나 d의 좌표 둘 중 하나를 출력해주면 된다.

 

이제 모든 경우가 해결이 되었다.

코드는 아래의 접은 글에 정리되어있다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int x, y; };

bool operator== (s a, s b) {
    if(a.x == b.x && a.y == b.y) return true;
    else return false;
}
bool operator>= (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y >= b.y)) return true;
    else return false;
}
bool operator<= (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y <= b.y)) return true;
    else return false;
}
bool operator> (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y > b.y)) return true;
    else return false;
}
bool operator< (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
    else return false;
}

int ccw(s a, s b, s c) {
    int val = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);

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

void coor(s a, s b, s c, s d) {
    double X = (a.x * b.y - a.y * b.x) * (c.x - d.x) - (a.x - b.x) * (c.x * d.y - c.y * d.x);
    double Y = (a.x * b.y - a.y * b.x) * (c.y - d.y) - (a.y - b.y) * (c.x * d.y - c.y * d.x);
    double div = (a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x);

    if(div == 0) {
        if(b == c && a <= c) cout << b.x << " " << b.y << "\n";
        else if(a == d && c <= a) cout << a.x << " " << a.y << "\n";
    }
    else cout << X / div << " " << Y / div << "\n";
}

void inter(s a, s b, s c, s d) {
    int val1 = ccw(a, b, c) * ccw(a, b, d);
    int val2 = ccw(c, d, a) * ccw(c, d, b);

    if(val1 == 0 && val2 == 0) {
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);

        if(a <= d && b >= c) {
            cout << 1 << "\n";
            coor(a, b, c, d);
        }
        else cout << 0 << "\n";
    }
    else {
        if(val1 <= 0 && val2 <= 0) {
            cout << 1 << "\n";
            coor(a, b, c, d);
        }
        else cout << 0 << "\n";
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<s> p(4);
    for(int i=0; i<4; i++) cin >> p[i].x >> p[i].y;

    cout << fixed;
    cout.precision(9);

    inter(p[0], p[1], p[2], p[3]);
}

 

 

백준 BOJ 10255번 : 교차점

문제 난이도 : Platinum IV

알고리즘 분류 : 기하학, 선분 교차 판정

 

직사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표, 그리고 선분이 주어졌을 때 선분과 직사각형의 교점의 개수를 구하는 문제이다. (만약 무수히 많은 점이 겹친다면 4를 출력한다.)

 

직사각형의 4개의 변 각각에 대해 선분과의 교차 여부를 확인해주면 된다.

만약 하나라도 선분이 겹치는 경우가 있으면 4를 출력해주면 된다.

문제는 직사각형의 꼭짓점과 선분이 만나는 경우인데 이 경우에는 만난 꼭짓점의 개수만큼 다시 빼주어야 한다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int x, y; };

bool operator== (s a, s b) {
    if(a.x == b.x && a.y == b.y) return true;
    else return false;
}
bool operator>= (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y >= b.y)) return true;
    else return false;
}
bool operator<= (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y <= b.y)) return true;
    else return false;
}
bool operator> (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y > b.y)) return true;
    else return false;
}
bool operator< (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
    else return false;
}

int ccw(s a, s b, s c) {
    int val = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);

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

bool cross, overlap;
double cx, cy;

void coor(s a, s b, s c, s d) {
    double X = (a.x * b.y - a.y * b.x) * (c.x - d.x) - (a.x - b.x) * (c.x * d.y - c.y * d.x);
    double Y = (a.x * b.y - a.y * b.x) * (c.y - d.y) - (a.y - b.y) * (c.x * d.y - c.y * d.x);
    double div = (a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x);

    if(div == 0) {
        if(b == c && a <= c) cx = b.x, cy = b.y, overlap = false;
        else if(a == d && c <= a) cx = a.x, cy = a.y, overlap = false;
        else overlap = true;
    }
    else cx = X / div, cy = Y / div, overlap = false;
}

void inter(s a, s b, s c, s d) {
    int val1 = ccw(a, b, c) * ccw(a, b, d);
    int val2 = ccw(c, d, a) * ccw(c, d, b);

    if(val1 == 0 && val2 == 0) {
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);

        if(a <= d && b >= c) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
    else {
        if(val1 <= 0 && val2 <= 0) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cout << fixed;
    cout.precision(9);

    int T; cin >> T;

    while(T--) {
        vector<s> v(6);

        cin >> v[0].x >> v[0].y >> v[2].x >> v[2].y;
        cin >> v[4].x >> v[4].y >> v[5].x >> v[5].y;

        v[1].x = v[2].x, v[1].y = v[0].y;
        v[3].x = v[0].x, v[3].y = v[2].y;

        int cnt = 0, ver = 0;
        bool inf = false;

        for(int i=0; i<4; i++) {
            inter(v[i], v[(i+1)%4], v[4], v[5]);

            if(cross && overlap) inf = true;
            else if(cross) {
                bool check = false;

                for(int i=0; i<4; i++)
                    if(cx == v[i].x && cy == v[i].y) check = true;

                if(check) ver++;

                cnt++;
            }
        }

        if(inf) cout << 4 << "\n";
        else {
            cnt -= ver/2;

            cout << cnt << "\n";
        }
    }
}

 

 

백준 BOJ 16491번 : 대피소 찾기

문제 난이도 : Platinum V

알고리즘 분류 : 기하학, 선분 교차 판정, 브루트포스

 

N개의 로봇이 N개의 대피소로 한 로봇 당 하나의 대피소에 이동할 때, 직선으로 이동하는 로봇들이 서로 동선이 겹치지 않게 하기 위해 각각 이동해야하는 대피소 번호를 구하는 문제이다.

 

일단 브루트포스 방식으로 로봇들을 각 대피소에 가능한 모든 매치를 해주고, 각 매치에 대해서 두 지점을 연결한 선분 N개가 서로 교차하는지 체크해주면 된다.

나의 경우에는 매치하는 과정을 next_permutation을 이용해서 풀었다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int x, y; };

bool operator== (s a, s b) {
    if(a.x == b.x && a.y == b.y) return true;
    else return false;
}
bool operator>= (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y >= b.y)) return true;
    else return false;
}
bool operator<= (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y <= b.y)) return true;
    else return false;
}
bool operator> (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y > b.y)) return true;
    else return false;
}
bool operator< (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
    else return false;
}

int ccw(s a, s b, s c) {
    int val = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);

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

bool cross, overlap;
double cx, cy;

void coor(s a, s b, s c, s d) {
    double X = (a.x * b.y - a.y * b.x) * (c.x - d.x) - (a.x - b.x) * (c.x * d.y - c.y * d.x);
    double Y = (a.x * b.y - a.y * b.x) * (c.y - d.y) - (a.y - b.y) * (c.x * d.y - c.y * d.x);
    double div = (a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x);

    if(div == 0) {
        if(b == c && a <= c) cx = b.x, cy = b.y, overlap = false;
        else if(a == d && c <= a) cx = a.x, cy = a.y, overlap = false;
        else overlap = true;
    }
    else cx = X / div, cy = Y / div, overlap = false;
}

void inter(s a, s b, s c, s d) {
    int val1 = ccw(a, b, c) * ccw(a, b, d);
    int val2 = ccw(c, d, a) * ccw(c, d, b);

    if(val1 == 0 && val2 == 0) {
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);

        if(a <= d && b >= c) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
    else {
        if(val1 <= 0 && val2 <= 0) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<s> v(N), u(N);
    for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y;
    for(int i=0; i<N; i++) cin >> u[i].x >> u[i].y;

    vector<int> w(N);
    for(int i=0; i<N; i++) w[i] = i;

    while(true) {
        bool check = true;

        for(int i=0; i<N; i++)
            for(int j=i+1; j<N; j++) {
                inter(v[i], u[w[i]], v[j], u[w[j]]);

                if(cross) check = false;
            }

        if(check) {
            for(int i=0; i<N; i++) cout << w[i] + 1 << "\n";

            break;
        }

        if(!next_permutation(w.begin(), w.end())) break;
    }
}

 

 

백준 BOJ 2162번 : 선분 그룹

문제 난이도 : Gold I

알고리즘 분류 : 기하학, 선분 교차 판정, 분리 집합

 

N개의 선분이 주어지고 한 점 이상에서 교차하는 것은 같은 그룹이라고 할 때, 몇 개의 그룹이 존재하는지와 가장 큰 그룹의 크기를 구하는 문제이다.

 

교차하는 선분들에 대해서, 분리 집합으로 같은 그룹으로 묶어주면 된다.

이제 교차 여부만 판별하면 되는데 이것은 위에서 구현한 방식으로 해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int x, y; };

bool operator== (s a, s b) {
    if(a.x == b.x && a.y == b.y) return true;
    else return false;
}
bool operator>= (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y >= b.y)) return true;
    else return false;
}
bool operator<= (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y <= b.y)) return true;
    else return false;
}
bool operator> (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y > b.y)) return true;
    else return false;
}
bool operator< (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
    else return false;
}

int ccw(s a, s b, s c) {
    int val = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);

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

bool cross, overlap;
double cx, cy;

void coor(s a, s b, s c, s d) {
    double X = (a.x * b.y - a.y * b.x) * (c.x - d.x) - (a.x - b.x) * (c.x * d.y - c.y * d.x);
    double Y = (a.x * b.y - a.y * b.x) * (c.y - d.y) - (a.y - b.y) * (c.x * d.y - c.y * d.x);
    double div = (a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x);

    if(div == 0) {
        if(b == c && a <= c) cx = b.x, cy = b.y, overlap = false;
        else if(a == d && c <= a) cx = a.x, cy = a.y, overlap = false;
        else overlap = true;
    }
    else cx = X / div, cy = Y / div, overlap = false;
}

void inter(s a, s b, s c, s d) {
    int val1 = ccw(a, b, c) * ccw(a, b, d);
    int val2 = ccw(c, d, a) * ccw(c, d, b);

    if(val1 == 0 && val2 == 0) {
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);

        if(a <= d && b >= c) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
    else {
        if(val1 <= 0 && val2 <= 0) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
}

vector<int> u;

int f(int x) {
    if(u[x] == x) return x;
    else return x = f(u[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cout << fixed;
    cout.precision(9);

    int N; cin >> N;

    vector<s> v(N*2);
    for(int i=0; i<N*2; i++) cin >> v[i].x >> v[i].y;

    u.resize(N);
    for(int i=0; i<N; i++) u[i] = i;

    for(int i=0; i<N; i++)
        for(int j=i+1; j<N; j++) {
            inter(v[i*2], v[i*2 + 1], v[j*2], v[j*2 + 1]);

            if(cross && f(i) != f(j)) u[f(i)] = f(j);
        }

    vector<int> w;

    for(int i=0; i<N; i++) w.push_back(f(i));

    sort(w.begin(), w.end());
    w.erase(unique(w.begin(), w.end()), w.end());

    cout << w.size() << "\n";

    w.clear();
    w.resize(N);

    for(int i=0; i<N; i++) w[f(i)]++;

    int Max = 0;
    for(int i=0; i<N; i++) Max = max(Max, w[i]);

    cout << Max << "\n";
}

 

 

백준 BOJ 17387번 : 선분 교차 2

문제 난이도 : Gold II

알고리즘 분류 : 기하학, 선분 교차 판정

 

두 선분의 끝 점의 좌표가 주어질 때, 두 선분의 교차 여부를 구하는 문제이다.

 

위의 문제와 달리 교차점의 좌표를 구하지 않아도 되므로, 위 문제의 하위 버전임을 알 수 있다.

위 문제의 풀이 코드에서 coor 함수 부분만 지워주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int x, y; };

bool operator== (s a, s b) {
    if(a.x == b.x && a.y == b.y) return true;
    else return false;
}
bool operator>= (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y >= b.y)) return true;
    else return false;
}
bool operator<= (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y <= b.y)) return true;
    else return false;
}
bool operator> (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y > b.y)) return true;
    else return false;
}
bool operator< (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
    else return false;
}

int ccw(s a, s b, s c) {
    int val = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);

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

void inter(s a, s b, s c, s d) {
    int val1 = ccw(a, b, c) * ccw(a, b, d);
    int val2 = ccw(c, d, a) * ccw(c, d, b);

    if(val1 == 0 && val2 == 0) {
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);

        if(a <= d && b >= c) cout << 1 << "\n";
        else cout << 0 << "\n";
    }
    else {
        if(val1 <= 0 && val2 <= 0) cout << 1 << "\n";
        else cout << 0 << "\n";
    }
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<s> p(4);
    for(int i=0; i<4; i++) cin >> p[i].x >> p[i].y;

    cout << fixed;
    cout.precision(9);

    inter(p[0], p[1], p[2], p[3]);
}

 

 

백준 BOJ 1558번 : 그림의 개수

문제 난이도 : Gold II

알고리즘 분류 : 기하학, 선분 교차 판정, 분리 집합

 

연속된 선분으로 이루어졌고 각 선분의 시작점이 이전 점인 선분의 집합을 폴리라인이라고 할 때, N개의 폴리라인이 주어졌을 때 하나의 점이라도 공유하면 같은 그림이라고 한다면 몇 개의 그림이 존재하는지 구하는 문제이다.

 

4중 for문으로 모든 폴리라인 쌍의 모든 선분 쌍에 대해 하나라도 교차가 있으면 분리 집합을 이용하여 같은 그룹으로 처리해준 뒤 마지막에 그룹의 개수를 세어주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct s { int x, y; };

bool operator== (s a, s b) {
    if(a.x == b.x && a.y == b.y) return true;
    else return false;
}
bool operator>= (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y >= b.y)) return true;
    else return false;
}
bool operator<= (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y <= b.y)) return true;
    else return false;
}
bool operator> (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y > b.y)) return true;
    else return false;
}
bool operator< (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
    else return false;
}

int ccw(s a, s b, s c) {
    int val = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);

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

bool cross, overlap;
double cx, cy;

void coor(s a, s b, s c, s d) {
    double X = (a.x * b.y - a.y * b.x) * (c.x - d.x) - (a.x - b.x) * (c.x * d.y - c.y * d.x);
    double Y = (a.x * b.y - a.y * b.x) * (c.y - d.y) - (a.y - b.y) * (c.x * d.y - c.y * d.x);
    double div = (a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x);

    if(div == 0) {
        if(b == c && a <= c) cx = b.x, cy = b.y, overlap = false;
        else if(a == d && c <= a) cx = a.x, cy = a.y, overlap = false;
        else overlap = true;
    }
    else cx = X / div, cy = Y / div, overlap = false;
}

void inter(s a, s b, s c, s d) {
    int val1 = ccw(a, b, c) * ccw(a, b, d);
    int val2 = ccw(c, d, a) * ccw(c, d, b);

    if(val1 == 0 && val2 == 0) {
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);

        if(a <= d && b >= c) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
    else {
        if(val1 <= 0 && val2 <= 0) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
}

vector<int> u;

int f(int x) {
    if(x == u[x]) return x;
    else return x = f(u[x]);
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<vector<s>> v(N);
    for(int i=0; i<N; i++) {
        int M; cin >> M;

        while(M--) {
            s tmp; cin >> tmp.x >> tmp.y;

            v[i].push_back(tmp);
        }

        if(v[i].size() == 1) v[i].push_back(v[i].back());
    }

    u.resize(N);
    for(int i=0; i<N; i++) u[i] = i;

    for(int i=0; i<N; i++)
        for(int j=i+1; j<N; j++) {
            bool check = false;

            for(int k=1; k<v[i].size(); k++)
                for(int l=1; l<v[j].size(); l++) {
                    inter(v[i][k-1], v[i][k], v[j][l-1], v[j][l]);

                    if(cross) check = true;
                }

            if(check && f(i) != f(j)) u[f(i)] = f(j);
        }

    vector<int> w;
    for(int i=0; i<N; i++) w.push_back(f(i));

    sort(w.begin(), w.end());
    w.erase(unique(w.begin(), w.end()), w.end());

    cout << w.size() << "\n";
}