글 읽기 - 어디가 틀렸는지 알려주실수 있나요 ㅎㅎㅎ

ansemddl97 6년 전 0

Graham's Scan으로 볼록껍질을 구한뒤 회전하는 캘리퍼스로 가장 먼 점을 구하려고했습니다.

예제는 잘 출력되는데 틀린 부분을 어디서 찾아야 할지 막막하네요 ㅎㅎ;;

#include <stdio.h>
#include <algorithm>
#include <stack>
#include <math.h>

using namespace std;

typedef pair<int, int> pii;

pii arr[100010];
pii ans[100010];
int num, len;
bool comp1(pii &A, pii &B) {
	return A.first * B.second > A.second * B.first;
}

bool comp2(pii &A, pii &B) {
	if (A.second != B.second) return A.second < B.second;
	else return A.first < B.first;
}

const pii operator -(const pii &A) {
	return { -A.first, -A.second };
}

const pii operator -(const pii &A, const pii &B) {
	return { A.first - B.first, A.second - B.second };
}

const pii operator +(const pii &A, const pii &B) {
	return { A.first + B.first, A.second + B.second };
}

int ccw(pii &A, pii &B, pii &C) {
	return (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
}

double dist(pii const &A, pii const &B) {
	return sqrt(pow(A.first - B.first, 2.0) + pow(A.second - B.second, 2.0));
}

double get_angle(const pii &A, const pii &B) {
	return acos((A.first * B.first + A.second * B.second) / dist(make_pair(A.first, A.second), make_pair(0, 0)) / dist(make_pair(B.first, B.second), make_pair(0, 0)));
}

int main(void)
{
	scanf("%d", &num);
	for (int i = 1; i <= num; i++) scanf("%d%d", &arr[i].first, &arr[i].second);

	sort(arr + 1, arr + 1 + num, comp2);

	for (int i = 2; i <= num; i++) arr[i] = arr[i] - arr[1];
	sort(arr + 2, arr + num + 1, comp1);
	for (int i = 2; i <= num; i++) arr[i] = arr[i] + arr[1];

	stack<int> st;
	st.push(1);	st.push(2);
	for (int i = 3; i <= num; i++) {
		while (st.size() > 1) {
			int t1 = st.top();
			st.pop();
			int t2 = st.top();

			if (ccw(arr[t2], arr[t1], arr[i]) > 0) {
				st.push(t1);
				break;
			}
		}
		st.push(i);
	}

	len = st.size();

	int P = 1, Q = len;
	for (int i = 1; i <= len; i++) {
		ans[len - i + 1] = arr[st.top()];
		if (arr[st.top()].second > ans[Q].second) Q = len - i + 1;
		if (arr[st.top()].second == ans[Q].second && arr[st.top()].first > ans[Q].first)  Q = len - i + 1;
		st.pop();
	}

	pii Pv = { 1, 0 };
	double answer = dist(ans[P], ans[Q]);
	for (int i = 1; i <= len * 2; i++) {
		double Pa = get_angle(Pv, ans[(P % len) + 1] - ans[P]);
		double Qa = get_angle(-Pv, ans[(Q % len) + 1] - ans[Q]);

		if (Pa <= Qa) {
			Pv = ans[(P % len) + 1] - ans[P];
			P = (P % len) + 1;
		}

		else {
			Pv = -(ans[(Q % len) + 1] - ans[Q]);
			Q = (Q % len) + 1;
		}

		answer = max(answer, dist(ans[P], ans[Q]));
	}

	printf("%0.10lf", answer);
	return 0;
}

sgchoi5 6년 전 0

NCPC 문제는 공개된 정보가 많으니 참고하시면 되겠네요.. : )

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

어디가 틀렸는지 알려주실수 있나요 ㅎㅎㅎ

ansemddl97 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말