글 읽기 - Convex-Hull(볼록껍질) 54%에서자꾸 틀립니다. 고수님들..

donghy9508 5년 전 0

54%에서 자꾸틀리는데 질문게시판 정주행해보고 TC도 돌려봤는데 이상이 없습니다.

오버플로우도 방지했구요 ㅠ

셀프해결했습니다. ㅠ,ㅠ

코드는 같은문제로 힘들어하는사람을위해 남겨놓겠습니다.

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
typedef struct pos {
	int x;
	int y;
	//default constructor
	pos(){}
	//constructor
	pos(int ax, int ay) { x = ax, y = ay; }
	//operator
	pos operator-(const pos &b) {
		return pos(x - b.x, y - b.y);
	}
}pos;
pos arr[100001];
//첫 정렬;
pos piv;
bool cmp1(pos a, pos b) {
	if (a.y != b.y) return a.y < b.y;
	return a.x < b.x;
}
//두번째 외적을 이용한 정렬;
//180도 이내에서
//두 점의 외적이 양수면 각도 계산 가능
//한점이 (0,0)이고 두 점일 경우 외적은 ad-bc  (a,b) (c,d) 일때
long long cross(pos a, pos b) {
	return 1LL*a.x*b.y - 1LL * a.y*b.x;
}
//오류부분 54%
bool cmp2(pos a, pos b) {
    //셀프 해결한 부분.
    /*기존코드
	return cross(a - piv, b - piv) > 0;
    */
    long long crossProduct = cross(a-piv, b-piv);
    //일직선상에 위치해있을때도 처리를 해줘야 한다!
	if (crossProduct == 0) {
		if (a.y != b.y) return a.y < b.y;
		return a.x < b.x;
	}
	return crossProduct > 0;
}
//세점의 외적을 통해 각도계산 가능
//left turn, right turn;  >0 ->leftturn 
long long ccw(pos a, pos b, pos c) {
	return 1LL*a.x*b.y + 1LL*b.x*c.y + 1LL * c.x*a.y - 1LL * b.x*a.y - 1LL * c.x*b.y - 1LL * a.x*c.y;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &arr[i].x, &arr[i].y);
	}
	sort(arr, arr + n, cmp1);
	piv = arr[0];
	//기준점 제외 외적을 통한 각도정렬 
	sort(arr + 1, arr + n, cmp2);
	stack<pos> s;
	s.push(arr[0]);
	s.push(arr[1]);
	for (int i = 2; i < n; ) {
		while (s.size() >= 2) {
			pos first, second;
			second = s.top();
			s.pop();
			first = s.top();
			long long crossProduct = ccw(first, second, arr[i]);
			if (crossProduct > 0) {
				s.push(second);
				break;
			}
		}
		s.push(arr[i++]);
	}
	printf("%d\n", s.size());
}

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

문제

문제

출처

ICPC

Convex-Hull(볼록껍질) 54%에서자꾸 틀립니다. 고수님들..

donghy9508 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말