글 읽기 - Segfault 원인이 대체 뭘까요??

ababc1005 2년 전 0

3일가까이 보고있는데 전혀 모르겠습니다.

C++ 시작한지 이제 막 두달쯤 되어서 아직 디버깅이나 에러들에 익숙하지 않아서 그런지 ㅠㅠ

눈씻고 찾아봐도 모르겠네요.

vector를 사용하다보니 처음에는 당연히 index 접근이 잘못된거겠지.. 하고

모든 []를 at()으로 바꿔보았는데도 여전히 Segfault가 나오네요...

혹시 가능한 Segfault 요인이 무엇이있을까요??

알고리즘의 전반적인 코드들은 유사한 문제들에서는 전부 AC받았던 코드들이라

진짜 원인이 뭔지...

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>

#define MAX 10001

using namespace std;

class Vector2{
    public:
        long long x, y;
        Vector2(){
            x = 0; y = 0;
        }
        Vector2(long long _x, long long _y){
            x = _x; y = _y;
        }
        Vector2 operator+(Vector2 B){
            return Vector2(x+B.x, y+B.y);
        }
        Vector2 operator-(Vector2 B){
            return Vector2(x-B.x, y-B.y);
        }
        long long operator&(Vector2 B){
            return x*B.x + y*B.y;
        }
        long long operator^(Vector2 B){
            return x*B.y - y*B.x;
        }
        Vector2 operator/(long long k){
            return Vector2(x/k, y/k);
        }
        long long size(){
            return x*x + y*y;
        }
        void print(){
            cout << x << ' ' << y << '\n';
        }
};

class Poly{
    public:
        vector<Vector2> P;
        Poly(int N){
            P.resize(N);
        }
        Poly(vector<Vector2> _P){
            P = _P;
            long long minY = MAX;
            long long minX = MAX;
            int minI = 0;
            for(int i = 0; i < P.size(); i ++){
                if(minX > P.at(i).x){minX = P.at(i).x; minY = P.at(i).y; minI = i;}
                else if(minX == P.at(i).x && minY > P.at(i).y){minY = P.at(i).y; minI = i;}
            }
            Vector2 ref = P.at(minI);
            for(int i = 0; i < P.size(); i ++) P.at(i) = P.at(i) - ref;
            sort(P.begin(), P.end(), Poly::compare);
            for(int i = 0; i < P.size(); i ++) P.at(i) = P.at(i) + ref;
        }
        bool convexHull(){
            if(P.size() <= 2) return true;
            vector<Vector2> res(P.size() + 1);
            res.at(0) = P.at(0);
            res.at(1) = P.at(1);

            int index = 1;
            for(int i = 2; i <= P.size(); i ++){
                bool skip = false;
                while(index > 0){
                    if(((res.at(index) - res.at(index-1)) ^ (P.at(i%P.size()) - res.at(index))) < 0) index --;
                    else if(((res.at(index) - res.at(index-1)) ^ (P.at(i%P.size()) - res.at(index))) == 0){
                        if(((res.at(index) - res.at(index-1)) & (P.at(i%P.size()) - res.at(index))) >= 0) index --;
                        else{
                            if(i == P.size()) index++;
                            skip = true; 
                            break;
                        }
                    }
                    else break;
                }
                if(skip) continue;
                index ++;
                res.at(index) = P.at(i%P.size());
            }
            res.resize(index);
            P = res;
            return true;
        }
        long long rotCalipers(){
            if(P.size() == 1) return 0;
            if(P.size() == 2) return (P.at(0) - P.at(1)).size();
            
            long long ans = 0;
            int index = 1;
            for(int i = 0; i < P.size(); i ++){
                while((P.at((index + 1)%(P.size())) - P.at(i)).size() > (P.at(index%P.size()) - P.at(i)).size()){
                    index ++;
                }
                index %= P.size();
                if(ans < (P.at(index) - P.at(i)).size()) ans = (P.at(index) - P.at(i)).size();
            }
            return ans;
        }
        static bool compare(Vector2 A, Vector2 B){
            if((A^B) > 0) return true;
            else if((A^B) < 0) return false;
            else{
                if(A.size() == 0) return true;
                else if(B.size() == 0) return false;    
                else return A.size() > B.size();
            }
        }
        void print(){
            for(int i = 0; i < P.size(); i ++) P.at(i).print();
        }
};



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

    int N;
    cin >> N;
    vector<Vector2> _P(N);
    for(int i = 0; i < N; i ++){
        long long a, b;
        cin >> a >> b;
        _P.at(i) = Vector2(a, b);
    }

    Poly p(_P);
    p.convexHull();
    cout << p.rotCalipers();

    return 0;
}

WeissBlume 2년 전 2

std::sort의 비교 함수는 Strict Weak Ordering 조건을 만족해야 합니다.

For all a, comp(a,a)==false
If comp(a,b)==true then comp(b,a)==false
if comp(a,b)==true and comp(b,c)==true then comp(a,c)==true

Poly::compare의 경우 <0, 0>과 <0, 0>을 비교할 경우 comp(a, b) == true, comp(b, a) == true가 됩니다.

WeissBlume 2년 전 2

테스트용 데이터: 2049.in

ababc1005 2년 전 0

와!!!!! 감사합니다. 덕분에 또 몰랐던걸 알고가네요 ㅠㅠ

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

문제

문제

출처

ICPC

Segfault 원인이 대체 뭘까요??

ababc1005 2년 전 0

WeissBlume 2년 전 2

WeissBlume 2년 전 2

ababc1005 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말