글 읽기 - 답은 맞췄는데 이 코드는 왜 안되는건지 모르겠습니다.

dkak14 2년 전 0

compare 함수와 compare2 함수 순서대로 정렬하는 방식으로 정답을 맞추긴 했지만

기존에 썼던 compare3 함수만으로 정렬시킨것은 왜 안되는건지 모르겠습니다.

compare3 함수는 기준점으로부터의 각도가 더 큰 것이 뒤로 가게 해놓은건데 이러면 반시계 방향으로

정렬되니 되는게 아닌가요?

#include <iostream>
#include <string>
#include <memory.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;

long long point[100005][3];
int N;
vector<int> sortList;

long long Cross(int x1, int y1, int x2, int y2) {
	return (long long)x1 * y2 - (long long)x2 * y1;
}
long long CCW(int p1, int p2, int p3) {
	int x1 = point[p2][0] - point[p1][0];
	int x2 = point[p3][0] - point[p1][0];
	int y1 = point[p2][1] - point[p1][1];
	int y2 = point[p3][1] - point[p1][1];
	return Cross(x1, y1, x2, y2);
}
long long Angle(int x1, int y1, int x2, int y2) {
	long long angle = atan2(y2 - y1, x2 - x1);
	if (angle != 0)
		angle = angle * (long long)(180 / 3.14159f);
	else
		angle = 0;
	return angle;
}
long long dist(int x1, int y1, int x2, int y2) {
	long long x = (long long)x2 - x1;
	long long y = (long long)y2 - y1;
	long long d = sqrt(x * x + y * y);
	return d;
}
bool compare(int a, int b) {
	int x0 = point[sortList[0]][0];
	int y0 = point[sortList[0]][1];
	int x1 = point[a][0];
	int y1 = point[a][1];
	int x2 = point[b][0];
	int y2 = point[b][1];

	if (y1 == y2) {
		return x1 < x2;
	}
	else {
		return y1 < y2;
	}
}
bool compare2(int a, int b) {
	int x0 = point[sortList[0]][0];
	int y0 = point[sortList[0]][1];
	int x1 = point[a][0];
	int y1 = point[a][1];
	int x2 = point[b][0];
	int y2 = point[b][1];

	long long ccw = CCW(sortList[0], a, b);
	if (ccw == 0) {
		return dist(x0, y0, x1, y1) < dist(x0, y0, x2, y2);
	}
	return ccw > 0;
}
bool compare3(int a, int b) {
	return point[a][2] < point[b][2];
}
int main() {
	cin >> N;

	int minY = 1000000;
	int minX = 1000000;
	int minYIndex = 0;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		point[i][0] = x;
		point[i][1] = y;
		if (y <= minY && x <= minX) {
			minY = y;
			minX = x;
			minYIndex = i;
		}
	}
	point[minYIndex][2] = -1;
	sortList.push_back(minYIndex);
	for (int i = 0; i < N; i++) {
		if (i == minYIndex)
			continue;
		int x1 = 1;
		int y1 = 0;
		int x2 = point[i][0] - point[minYIndex][0];
		int y2 = point[i][1] - point[minYIndex][1];
		long long angle = Angle(x1, y1, x2, y2);

		point[i][2] = angle;
		sortList.push_back(i);
	}

	sort(sortList.begin() + 1, sortList.end(), compare3);

	for (int index = 0; index < sortList.size(); index++) {
		int prev = index - 1 < 0 ? sortList.size() - 1 : index - 1;
		int next = index + 1 > sortList.size() - 1 ? 0 : index + 1;
		long long ccw = CCW(sortList[prev], sortList[index], sortList[next]);

		if (ccw <= 0) {
			sortList.erase(sortList.begin() + index);
			index -= 2;
		}
	}

	cout << sortList.size();
}

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

문제

문제

출처

ICPC

답은 맞췄는데 이 코드는 왜 안되는건지 모르겠습니다.

dkak14 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말