글 읽기 - 무엇이;; 틀린걸까여 ;;

octo756 4년 전 1

틀린게 없어보이는데;;

고수분들 한번만 확인부탁드릴게여

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int N;
struct node {
	int xpos;
	int ypos;
	int pX;
	int qY;
};
bool cmp(node a, node b) {
	if (1LL * a.qY * b.pX != 1LL * a.pX * b.qY) return 1LL * a.qY * b.pX < 1LL * a.pX * b.qY;
	if (a.ypos != b.ypos) return a.ypos < b.ypos;
	return a.xpos < b.xpos;
}
node arr[100005];
stack<int> stk;

int main() {
	cin >> N;
	for (int n = 0; n < N; n++) {
		cin >> arr[n].xpos >> arr[n].ypos;
	}
	
	sort(arr, arr + N, cmp);

	for (int n = 1; n < N; n++) {
		arr[n].pX = arr[n].xpos - arr[0].xpos;
		arr[n].qY = arr[n].ypos - arr[0].ypos;
	}
	sort(arr + 1, arr + N, cmp);

	stk.push(0);
	stk.push(1);
	int next = 2;

	while (next < N) {
		while (stk.size() >= 2) {
			int first = stk.top();
			stk.pop();
			int second = stk.top();

			int secondX = arr[second].xpos;
			int secondY = arr[second].ypos;
			int firstX = arr[first].xpos;
			int firstY = arr[first].ypos;
			int nextX = arr[next].xpos;
			int nextY = arr[next].ypos;
			int vec1X = secondX - firstX;
			int vec1Y = secondY - firstY;
			int vec2X = nextX - firstX;
			int vec2Y = nextY - firstY;
			
			long long ccw = 1LL * vec1X * vec2Y - 1LL * vec1Y * vec2X;
			if(ccw > 0){
				stk.push(first);
				break;
			}
		}
		stk.push(next++);
	}
	cout << stk.size();
}

crypt9 4년 전 0

line 51,52 에서 CCW 계산 시,

벡터 (second ~ first) 와 벡터 (first ~ next) 를 비교해야 하는데,

벡터 (first ~ second) 과 벡터 (first ~ next) 로 계산 하셨네요.

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

문제

문제

출처

ICPC

무엇이;; 틀린걸까여 ;;

octo756 4년 전 1

crypt9 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말