convex hull 구현 문제입니다 ㅠㅠ

  • kun452
    kun452

    convex hull 문제를 풀고있는데 오답이 뜨네요 ㅠㅠ
    문제는 점의 집합이 주어질 때 볼록껍질을 이루는 점의 갯수 출력입니다 ㅠ

    #include <stdio.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

struct ab{
    int x;
    int y;
    double tan;
};

bool Func(ab a, ab b){ 
    return (a.tan < b.tan); 
}
bool Func2(ab a, ab b){
    return (b.tan < a.tan);
}

int main(){
    int n;
    cin >> n;


    int *x = new int[n];
    int *y = new int[n];

    for(int i=0; i<n; i++){
        cin >> x[i] >> y[i];
    }

    int index= 0;
    int MIN = y[0];

    for(int i=1; i<n; i++){
        if(MIN > y[i]){
            MIN = y[i];
            index = i;
        }

        if(MIN == y[i] && x[i] > x[index]){
            MIN = y[i];
            index = i;
        }
    }


    vector <ab> plus;
    vector <ab> minu;
    ab temp;

    for(int i=0; i<n; i++){
        if(i == index)
            continue;

        temp.x = x[i];
        temp.y = y[i];

        if(x[index] == x[i]){
            temp.tan = 987654321;
            plus.push_back(temp);
            continue;
        }

        if(y[index] == y[i]){
            temp.tan = 0;
            minu.push_back(temp);
            continue;
        }

        temp.tan = (double)(y[index] - y[i]) / (x[index] - x[i]);
        if(temp.tan >0){
            plus.push_back(temp);
        }else
            minu.push_back(temp);
    }

    sort(plus.begin(), plus.end(), Func);
    sort(minu.begin(), minu.end(), Func);

    //for(int i=0; i<plus.size() ;i++){
    //  cout << plus[i].x << " " << plus[i].y << " " << plus[i].tan<< endl;
    //}

    temp.x = x[index];
    temp.y = y[index];

    minu.push_back(temp);
    plus.push_back(temp);

    vector <ab> temp2;
    temp.x = x[index];
    temp.y = y[index];

    temp.tan = 0;
    temp2.push_back(temp);

    for(int i=0 ; i<plus.size(); i++){
        if(plus.size() == 1)
            break;
        if(i == plus.size() - 1 && minu.size() != 1){
            break;
        }
        if(i == 0)
            temp2.push_back(plus[i]);
        else{
            ab stac1 = temp2.back();
            temp2.pop_back();
            ab stac2 = temp2.back();
            temp2.pop_back();
            int v1_x, v1_y;
            int v2_x, v2_y;
            //cout << "다시" << endl;
            while(1){
                int v1_x = stac1.x - stac2.x;
                int v1_y = stac1.y - stac2.y;
                int v2_x = plus[i].x - stac1.x;
                int v2_y = plus[i].y - stac1.y;

                //cout << "재시작" << endl;
            //cout << "test " << plus[i].x << " " << plus[i].y << endl;
            //cout << "test " << stac1.x << " " << stac1.y << endl;
            //cout << "test " << stac2.x << " " << stac2.y << endl;

                double godojong = (double)(v1_x * v2_y - v1_y * v2_x);
                //cout << godojong << endl;
/*
                if(plus[i].x == stac1.x){
                    if(stac2.x >= stac1.x){
                        stac1 = stac2;
                        if(temp2.empty()){
                            temp2.push_back(stac2);
                            temp2.push_back(plus[i]);
                            break;
                        }
                        stac2 = temp2.back();

                        temp2.pop_back();
                    }else{
                        temp2.push_back(stac2);
                        temp2.push_back(stac1);
                        temp2.push_back(plus[i]);
                        break;
                    }

                }else if(plus[i].y == stac1.y){
                    //cout <<"뭐지" << endl;
                    if(stac2.y >= stac1.y){
                        stac1 = stac2;
                        stac2 = temp2.back();
                        temp2.pop_back();
                    }else{
                        temp2.push_back(stac2);
                        temp2.push_back(stac1);
                        temp2.push_back(plus[i]);
                        break;
                    }
                }
                else{*/
                    /*if((plus[i].y - stac1.y) * (stac2.x - stac1.x) >= (stac2.y - stac1.y) * (plus[i].x - stac1.x)){
                        cout <<"durl? " << endl;
                        stac1 = stac2;
                        if(temp2.empty()){
                            temp2.push_back(stac2);
                            temp2.push_back(plus[i]);
                            break;
                        }
                        stac2 = temp2.back();
                        temp2.pop_back();
                    }else{
                        cout << "dfdfdfdfdfsfdsfasfs " << endl;
                        temp2.push_back(stac2);
                        temp2.push_back(stac1);
                        temp2.push_back(plus[i]);
                        break;
                    }*/

                    if(godojong <= 0){
                        stac1 = stac2;
                        if(temp2.empty()){
                            temp2.push_back(stac2);
                            temp2.push_back(plus[i]);
                            break;
                        }
                        stac2 = temp2.back();
                        temp2.pop_back();
                    }else{
                        temp2.push_back(stac2);
                        temp2.push_back(stac1);
                        if(i == plus.size() - 1)
                            break;
                        temp2.push_back(plus[i]);
                        break;
                    }
                //}
            }
        }
    }


    for(int i = 0; i<minu.size(); i++){
        //cout << i << endl;
        ab stac1 = temp2.back();
        temp2.pop_back();
        ab stac2 = temp2.back();
        temp2.pop_back();
        //cout << "df " << i << " " << temp2.size()<< endl;
        while(1){
            int v1_x = stac1.x - stac2.x;
            int v1_y = stac1.y - stac2.y;
            int v2_x = minu[i].x - stac1.x;
            int v2_y = minu[i].y - stac1.y;


            double godojong = (double)(v1_x * v2_y - v1_y * v2_x);

            //cout << "test " << minu[i].x << " " << minu[i].y << endl;
            //cout << "test " << stac1.x << " " << stac1.y << endl;
            //cout << "test " << stac2.x << " " << stac2.y << endl;

            //cout << v1_x << " " << v1_y << " " << v2_x << " " << v2_y << endl;
            //cout << godojong << endl;

            /*if(minu[i].x == stac1.x){
                if(stac2.x <= stac1.x){
                    stac1 = stac2;
                    if(temp2.empty()){
                        temp2.push_back(stac2);
                        temp2.push_back(minu[i]);
                        break;
                    }
                    stac2 = temp2.back();
                    temp2.pop_back();
                }else{
                    temp2.push_back(stac2);
                    temp2.push_back(stac1);
                    temp2.push_back(minu[i]);
                    break;
                }

            }else if(minu[i].y == stac1.y){
                if(stac2.y <= stac1.y){
                    stac1 = stac2;
                    if(temp2.empty()){
                        temp2.push_back(stac2);
                        temp2.push_back(minu[i]);
                        break;
                    }
                    stac2 = temp2.back();
                    temp2.pop_back();
                }else{
                    //cout <<"hey" << endl;
                    temp2.push_back(stac2);
                    temp2.push_back(stac1);
                    temp2.push_back(minu[i]);
                    break;
                }
            }*/
            //else{
                /*double te = ((double)(stac2.y - stac1.y) / (stac2.x - stac1.x));
                if((minu[i].y - stac1.y) * (stac2.x - stac1.x) >= (stac2.y - stac1.y) * (minu[i].x - stac1.x)){
                    stac1 = stac2;
                    if(temp2.empty()){
                        temp2.push_back(stac2);
                        temp2.push_back(minu[i]);
                        break;
                    }
                    stac2 = temp2.back();
                    temp2.pop_back();
                }else{
                    temp2.push_back(stac2);
                    temp2.push_back(stac1);
                    temp2.push_back(minu[i]);
                    break;
                }*/

                if(godojong <= 0){
                    stac1 = stac2;
                    if(temp2.empty()){
                        temp2.push_back(stac2);
                        temp2.push_back(minu[i]);
                        break;
                    }
                    stac2 = temp2.back();
                    temp2.pop_back();
                }else{
                    temp2.push_back(stac2);
                    temp2.push_back(stac1);
                    if(i == minu.size() - 1)
                        break;
                    temp2.push_back(minu[i]);
                    break;
                }
            //}
        }
    }

    cout << temp2.size() << endl;

    return 0;
}

    9년 전
2개의 댓글이 있습니다.
  • kcm1700
    kcm1700

    일단 코드가 너무 길고 읽기가 힘들어서 어디가 문제가 되는지 알기 힘드네요. 쉬운 방법을 새로 배워서 짜보는 것은 어떨까요? 예를 들어 Andrew의 monotone chain convex hull 방법이 있어요.
    https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#C.2B.2B

    문제에서 한 선분 위에 세 개의 점이 있을 때 어떻게 세길 요구했는지도 중요하겠네요.


    9년 전 link
  • kun452
    kun452

    흠 그렇군요 저는 한선분에 세개의 점이 있는것을 대비해서 stack에 미리 지나온 점들을 넣어두고 벡터의 외적공식을 이용하여 그 값이 음수거나 0일때 해당점부터 지나온점들을 보면서 삭제하도록 하였습니다


    9년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.