글 읽기 - 알고리즘에 문제가 없을 것 같은데 어떤 반례가 있을까요?

ababc1005 2년 전 0

단순하게

두 다각형 꼭지점의 모든 합의 집함을 만든 뒤,

그 집합들을 포함하는 볼록 껍질을 구하고,

해당 볼록 다각형의 꼭지점 수와

꼭지점 자체를 출력하도록 했습니다.

볼록껍질을 구하는 알고리즘 자체는

다른 알고리즘에서도 사용했던 알고리즘이고,

중복점이 들어올 수도 있다는 점에만 주의해서 정렬과 그라함 스캔 코드를 살짝 수정했는데

계속 틀렸다고 나옵니다 ㅠㅠ

어떤경우가 문제가 되는건지 도저히 모르겠네요 ㅠㅠ

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

#define MAX 0x7FFFFFFF

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;
        }
        long long size(){
            return (x*x + y*y);
        }
        void print(){
            cout << x << ' ' << y <<'\n';
        }
};

class Poly{
    public:
        vector<Vector2> P;
        Poly(){}
        Poly(vector<Vector2> _P){
            P = _P;
        }
        void initialize(int N){
            P.resize(N);
            for(int i = 0; i < N; i ++){
                long long a, b;
                cin >> a >> b;
                P[i] = Vector2(a, b);
            }
        }

        void convexHull(){
            vector<Vector2> res(P.size() + 1);
            Vector2 ref;

            // find reference point
            long long minY = MAX;
            long long minX = MAX;
            int minI = 0;
            for(int i = 0; i < P.size(); i ++){
                if(P[i].y < minY){minY = P[i].y; minX = P[i].x; minI = i;}
                else if(P[i].y == minY && P[i].x < minX){minX = P[i].x; minI = i;}
            }
            ref = P[minI];
            
            // make delta array
            for(int i = 0; i < P.size(); i ++){
                P[i] = P[i] - ref;
            }

            // sort
            sort(P.begin(), P.end(), Poly::compare);

            // do graham scan
            res[0] = P[0];
            res[1] = P[1];
            int index = 1;
            for(int i = 2; i < P.size() + 1; i ++){
                int ci = i % P.size();
                while(!ccw(P[ci], res[index], res[index - 1]) && index > 0){
                    index --;
                }
                index ++;
                res[index] = P[ci];
            }
            res.resize(index);
            for(int i = 0; i < res.size(); i ++){
                res[i] = res[i] + ref;
            }
            P = res;
        }

        bool ccw(Vector2 A, Vector2 B, Vector2 C){
            if(((B-C)^(A-B)) > 0) return true;
            if(((B-C)^(A-B)) == 0){
                if((A-C).size() >= (B-C).size()) return false;
                else return true;
            }
            return false;
        }

        static bool compare(Vector2 A, Vector2 B){
            if(A.size() == 0) return true; // if A is origin, A should go first
            if(B.size() == 0) return false; // if B is origin, A should go late
            if((A ^ B) > 0) return true; // if B is on the left of A, A should go first
            if((A ^ B) == 0){ // if the angles are the same,
                if(A.y != 0) return A.y > B.y; // point with large y value goes first
                else return A.x < B.x; // and also if y value are same with 0, point with small x value goes first
            }   
            return false;
        }

        void print(){
            long long minX = MAX;
            long long minY = MAX;
            long long minI = 0;
            
            for(int i = 0; i < P.size(); i ++){
                if(P[i].x < minX) {minX = P[i].y; minY = P[i].y; minI = i;}
                else if(P[i].x == minX && P[i].y < minY) {minY = P[i].y; minI = i;}
            }    

            long long size = P.size();
            for(int i = 0; i < size; i ++){
                P[(i+minI)%size].print();
            }    
        }
};



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

    long long N, M;
    cin >> N >> M;

    Poly pN;
    pN.initialize(N);
    pN.convexHull();
    Poly pM;
    pM.initialize(M);
    pM.convexHull();
    
    vector<Vector2> p(pN.P.size()*pM.P.size());
    for(int i = 0; i < pN.P.size(); i ++){
        for(int j = 0; j < pM.P.size(); j ++){
            p[i*pM.P.size() + j] = pN.P[i] + pM.P[j];
        }
    }

    Poly Po(p);
    Po.convexHull();
    cout << Po.P.size() << '\n';
    Po.print();

    return 0;
}

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

문제

문제

출처

ICPC

알고리즘에 문제가 없을 것 같은데 어떤 반례가 있을까요?

ababc1005 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말