글 읽기 - 도움 부탁드립니다.

operaghost 7년 전 0

각도 정렬 함수 (cmp2)가 잘못 되었는지

아니면 while문에서 스택을 쓰는 부분에서 잘못 되었는지 잘 모르겠네요.

고수님들의 조언이 필요합니다.^^

#include<bits/stdc++.h>

using namespace std;

stack<int>s;

struct data{
    double x, y, angle;
}d[100010];

double cmp(const data &p, const data &q){
    if(p.y == q.y)return p. x< q.x;
    return p.y < q.y;
}

double cmp2(const data &p, const data &q){
    if(p.angle < 0 && q.angle > 0)return p.angle > q.angle;
    if(p.angle > 0 && q.angle < 0)return p.angle < q.angle;
    return p.angle < q.angle;
}
double ccw(data p, data q, data r){
    return (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
}
int main()
{
    ios::sync_with_stdio(false);

    int n, i, num;

    cin >> n;

    for(i=0; i<n; i++)cin >> d[i].x >> d[i].y;

    sort(d, d+n, cmp);

    for(i=1; i<n; i++){
        d[i].angle = (double)((d[i].y - d[0].y) / (d[i].x - d[0].x));
    }

    sort(d+1, d+n, cmp2);

    s.push(0);
    s.push(1);
    num=2;

    while(num < n){
        while(s.size() >= 2){
            int k2 = s.top();
            s.pop();
            int k1 = s.top();
            if(ccw(d[k1], d[k2], d[num]) >= 0){
                s.push(k2);
                break;
            }
        }
        s.push(num++);
    }

    cout<<s.size();
    return 0;
}

etaehyun4 7년 전 0

각도로 정렬을 하실 때 기울기를 쓰시게 되면 두 좌표의 x값이 같은 경우에는 division by zero 가 뜰 수도 있을 것 같네요

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

문제

문제

출처

ICPC

도움 부탁드립니다.

operaghost 7년 전 0

etaehyun4 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말