글 읽기 - 컨벡스헐 런타임 에러 질문드립니다!!

zerocow 3년 전 0

-구현 로직

1) 입력받은 좌표 x값 오름차순, x값 같을 시 y값 오름차순 정렬

2) 정렬 후 좌표의 첫 값인 pos[0]을 기준점으로 설정 후 나머지 점을 반시계방향을 정렬

정렬하기 위해 탄젠트 이용(-파이/2 ~ 파이/2까지는 오름차순임을 이용, 기준점 pos는 x좌표가 가장 작음을 이용)

0으로 나눌 가능성을 없애기 위해 x-pos[0].x == 0 인 경우는 예외 처리하였습니다

3) 순차적으로 ccw를 구하며 다각형에 속하는 점은 스택에 push

- 런타임 에러가 의심되었던 부분이

1) int범위 초과 : ccw계산 시에만 초과 가능성이 있는데 이 부분은 long long로 계산해주었습니다.

2) 탄젠트 계산 시 sort함수 : 0으로 나누진 않는 것 같은데 모르겠습니다...

어렵네요 ㅠㅠ 조언부탁드리겠습니다!

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stack>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;


class cmp{
    pii para;
    public:
    cmp(pii p) : para(p){}

    bool operator()(pii a, pii b){
	if(a.x == para.x && b.x == para.x) return a.y > b.y;
	if(a.x == para.x) return true;
	if(b.x == para.x) return true;
	if(a.y == para.y && b.y == para.y) return a.x < b.x;
	double ta = (a.y-para.y)/(double)(a.x-para.x);
	double tb = (b.y-para.y)/(double)(b.x-para.x);
	return ta < tb;
    }
};

int ccw(pii a, pii b, pii c){
    ll tmp = a.x*b.y+b.x*c.y+c.x*a.y;
    tmp -= b.x*a.y+c.x*b.y+a.x*c.y;
    if(tmp < 0) return -1;
    else if(tmp > 0) return 1;
    return 0;
}

int main(){
    int N;
    scanf("%d", &N);
    vector<pii> pos(N);
    for(int i = 0; i < N; i++)
	scanf("%d %d", &pos[i].x, &pos[i].y);

    sort(pos.begin(), pos.end());
    sort(pos.begin()+1, pos.end(), cmp(pos[0]));

    stack<pii> stk;
    stk.push(pos[0]);
    stk.push(pos[1]);

    for(int i = 2; i < N; i++){
	while(stk.size() >= 2){
	    pii p2 = stk.top();
	    stk.pop();
	    pii p1 = stk.top();
	    if(ccw(p1, p2, pos[i]) > 0){
		stk.push(p2);
		break;
	    }
	}
	stk.push(pos[i]);
    }

    pii p1 = stk.top();
    stk.pop();
    pii p2 = stk.top();
    if(ccw(p1, p2, pos[0]) != 0) stk.push(p1);
    printf("%d\n", stk.size());
    return 0;
}

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

문제

문제

출처

ICPC

컨벡스헐 런타임 에러 질문드립니다!!

zerocow 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말