글 읽기 - 유니온 파인드에 오류가 있는걸까요? (게시판 테케 모두 통과)

ababc1005 2년 전 0

선분 교차는 선분교차2 문제 AC받은 코드를 그대로 사용했고,

서로 다른 두가지 방식으로 구현했었는데, 두 가지 모두 사용해도 16% 동일한 위치에서 실패가 납니다.

전반적으로 long long을 사용해서 오버플로는 아닐 것이고...

유니온 파인드가 유력한 것 같은데

아무리 코드를 읽어봐도 어디서 틀렸는지 보이지가 않네요 ㅠㅠ

혹시 몰라서 매번 부모 확인하기 전에 루트 노드로 부모 노드 갱신도 해주고 있는데

제가 어디를 놓쳤을까요??

도움 주시면 정말 감사하겠습니다 ㅠㅠㅠ

#include<iostream>
#include<set>
using namespace std;

int sign(long long n){
    if(n > 0) return 1;
    else if(n < 0) return -1;
    else return 0;
}

class Line{
    public: 
        long long a, b, c;
        Line(long long _a, long long _b, long long _c){
            a = _a; b = _b; c = _c;
        }
        long long subst(long long x, long long y){
            return a*x + b*y + c;
        }

};

class Edge{
    public:
        Edge* parent;
        int size;
        long long x1, y1, x2, y2;
        Edge(){
            parent = this; size = 1;
            x1 = 0; y1 = 0; x2 = 0; y2 = 0;
        }
        Edge(long long _x1, long long _y1, long long _x2, long long _y2){
            parent = this; size = 1;
            x1 = _x1; y1 = _y1; x2 = _x2; y2 = _y2;
        }
        static bool intersact(Edge* e1, Edge* e2){
            long long x1 = e1 -> x1, y1 = e1 -> y1, x2 = e1 -> x2, y2 = e1 -> y2;
            long long x3 = e2 -> x1, y3 = e2 -> y1, x4 = e2 -> x2, y4 = e2 -> y2;

            int dir3 = sign((x3-x1)*(y2-y1) - (x2-x1)*(y3-y1));
            int dir4 = sign((x4-x1)*(y2-y1) - (x2-x1)*(y4-y1));
            int dir1 = sign((x1-x3)*(y4-y3) - (x4-x3)*(y1-y3));
            int dir2 = sign((x2-x3)*(y4-y3) - (x4-x3)*(y2-y3));

            if(dir1 == 0 && dir2 == 0){
                if(y2 - y1 > 0){
                    if(((y3 - y1) > (y2 - y1) && (y4 - y1) > (y2 - y1)) 
                    || (y3 - y1) * (y2 - y1) < 0 && (y4 - y1) * (y2 - y1) < 0) return false;
                    else return true;
                }else if(y2 - y1 < 0){
                    if(((y3 - y1) < (y2 - y1) && (y4 - y1) < (y2 - y1)) 
                    || (y3 - y1) * (y2 - y1) < 0 && (y4 - y1) * (y2 - y1) < 0) return false;
                    else return true;
                }else if(x2 - x1 > 0){
                    if(((x3 - x1) > (x2 - x1) && (x4 - x1) > (x2 - x1)) 
                    || (x3 - x1) * (x2 - x1) < 0 && (x4 - x1) * (x2 - x1) < 0) return false;
                    else return true;
                }else if(x2 - x1 < 0){
                    if(((x3 - x1) < (x2 - x1) && (x4 - x1) < (x2 - x1)) 
                    || (x3 - x1) * (x2 - x1) < 0 && (x4 - x1) * (x2 - x1) < 0) return false;
                    else return true;
                }
            }else{
                if(dir3 * dir4 <= 0 && dir1 * dir2 <= 0) return true;
                else return false;
            }
        }
        void root(){
            Edge* tmp = parent;
            while(tmp -> parent != tmp){
                tmp = tmp -> parent;
            }
            parent = tmp;
        }
};

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

    int N;
    cin >> N;

    Edge* edges[N];
    for(int i = 0 ; i < N; i ++){
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        edges[i] = new Edge(a, b, c, d);
        //cout << edges[i] -> parent << '\n';
    }

    for(int i = 0; i < N; i ++){
        for(int j = i+1; j < N; j ++){
            if(Edge::intersact(edges[i], edges[j])){
                edges[i] -> root();
                edges[j] -> root();
                if(edges[i] -> parent != edges[j] -> parent){
                    if(edges[i] -> parent -> size > edges[j] -> parent -> size){
                        edges[i] -> parent -> size += edges[j] -> parent -> size;
                        edges[j] -> parent = edges[i] -> parent;
                    }else{
                        edges[j] -> parent -> size += edges[i] -> parent -> size;
                        edges[i] -> parent = edges[j] -> parent;                    
                    }
                }
            }
        }
    }

    int ans = 0;
    set<Edge*> s;
    for(int i = 0; i < N; i ++){
        //cout << edges[i] -> parent << '\n';
        edges[i] -> root();
        s.insert(edges[i] -> parent);
    }
    cout << s.size() << '\n';
    for(set<Edge*>::iterator it = s.begin(); it != s.end(); it ++){
        if(ans < (*it) -> size) ans = (*it) -> size;
    }
    cout << ans << '\n';

    return 0;
}

ababc1005 2년 전 0

멍청하게도 i선분의 루트노드의 루트를 j노드의 루트노드로 바꾸는게 아니라 i선분의 루트노드만 바꾸고 있었네요...

부모의 부모의 부모의 부모의 부모의 하다보니 혼란에 빠져버린 :(

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

유니온 파인드에 오류가 있는걸까요? (게시판 테케 모두 통과)

ababc1005 2년 전 0

ababc1005 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말