글 읽기 - 어디부분에서 틀린지 잘 모르겠습니다. 반례 10만개를 비교해도 안나오네요 ㅠ

qktlf789456 2년 전 0

Convex Hull 을 구한 뒤 Convex Hull 의 각각의 변에 대해서 가장 먼 점까지의 거리를 구했고 각 변에 대해서 가장 먼 점이 최소인 것을 출력하도록 하였습니다.

다른 AC코드와 반례를 비교하는 프로그램을 짠 뒤 10만개이상을 비교했지만 반례가 나오지않았네요 ㅠ 맞고싶습니다 ㅠㅠ

#include <iostream>
#include <map>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>

#define SIZE 3000
#define EMPTY -124152

using namespace std;



int n;


struct node
{
	long long x, y;

};
struct node points[301];


char ccw(struct node& A, struct node& B, struct node& C)
{
	long long x1 = A.x;
	long long x2 = B.x;
	long long x3 = C.x;
	long long y1 = A.y;
	long long y2 = B.y;
	long long y3 = C.y;

	long long res_value = (x1 * y2 + x2 * y3 + x3 * y1 - x2 * y1 - x3 * y2 - x1 * y3);

	return (res_value > 0 ? 1 : (res_value == 0 ? 0 : -1));
}


bool struct_cmp(struct node& A, struct node& B)
{
	char res_value = ccw(points[0], A, B);

	if (!res_value)
	{
		if (A.x == B.x)
		{
			return (A.y < B.y);
		}

		return (A.x < B.x);
	}

	return res_value > 0;
}

struct node stack[301];
int top = 0;

long double calc(int idx1, int idx2)
{

	long double dist = sqrt((stack[idx1].x - stack[idx2].x) * (stack[idx1].x - stack[idx2].x) + (stack[idx1].y - stack[idx2].y) * (stack[idx1].y - stack[idx2].y));
	long double res = 0;



	struct node point_lists[3] = { stack[idx1],  stack[idx2], };

	for (int i = 0; i < top; i++)
	{
		if (i == idx1 || i == idx2)
			continue;

		point_lists[2] = stack[i];
		

		//삼각형넓이구하기

		long double area = 0;
		for (int i = 0; i < 3; i++)
		{
			area += point_lists[i].x * point_lists[(i + 1 == 3 ? 0 : i + 1)].y;
		}
		for (int i = 0; i < 3; i++)
		{
			area -= point_lists[i].y * point_lists[(i + 1 == 3 ? 0 : i + 1)].x;
		}
		if (area < 0)
			area = -area;

		long double final_dist = area / dist;


		final_dist *= 100;
		if (final_dist - (long long)final_dist)
		{
			final_dist += 1;
			final_dist = (long long)final_dist;
		}
		final_dist /= 100;

		res = max(res, final_dist);

	}
	return res;
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);	


	int case_cnt = 1;
	while (1)
	{
		cin >> n;

		if (!n)
			break;

		top = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> points[i].x >> points[i].y;

			if (i)
			{
				if (points[0].x > points[i].x || (points[0].x == points[i].x && points[0].y > points[i].y))
					swap(points[0], points[i]);
			}
		}

		sort(points + 1, points + n, struct_cmp);


		for (int i = 0; i < n; i++)
		{
			while (top >= 2 && ccw(stack[top - 2], stack[top - 1], points[i]) <= 0)
			{
				top--;
			}
			stack[top++] = points[i];
		}


		long double res = 9999999999999;

		
		for (int i = 0; i < top; i++)
		{
			res = min(res, calc(i, (i + 1 >= top ? 0 : i+1)   )   );
		}

		cout.precision(2);
		cout << fixed;
		cout << "Case " << case_cnt++ << ": " << res << "\n";
	}
		

	return 0;
}

byeongkeunahn 2년 전 3

일단 예제가 안 나오네요. 2.40 대신 2.41이 출력됩니다.

해결법은 생각보다 간단합니다.

97번째 줄에서 소수점 셋째자리 이하에 0이 아닌 수가 있는지 확인하려고 하셨는데요, 일반적으로 실수 연산을 할 때 0이 아닌지를 비교하려면 0과 비교하면 안 되고 아주 작은 "엡실론"과 비교하는 것이 정석입니다. 97번째 줄만 1e-12보다 큰지로 비교를 하도록 고치면 AC를 받을 수 있습니다.

메커니즘을 설명하자면 부동소수점 실수가 십진법이 아닌 이진법으로 표현되는 특성상 2.40과 가장 가까운 이진법 표현에서 2.40보다 아주 약간 컸을 것이고(아주 약간 작을 수도 있지만, 여기서는 운이 나쁩니다), 그 덕분에 97번째 줄은 해당 부동소수점 수를 올림해버리는 우를 범하게 되는 것입니다.

하지만 근본적으로 덜 골치아픈 방법은 부동소수점 연산을 아예 사용하지 않는 것입니다. 이 문제에서와 같이 절대/상대오차가 허용되지 않고 exact한 답을 구해야 하는 경우 우선 구하는 거리의 제곱을 분수꼴로 구하고, 여기에 100의 제곱인 10000을 곱해준 다음, 이분 탐색을 이용해 정수 수준에서 sqrt를 계산하는 방법이 가능합니다.

qktlf789456 2년 전 0

컴파일러마다 출력결과가 다른가봅니다 .. 그래서 예제가 계속 저는 2.40이 나온거같습니다.. 부동소수점문제를 항상 제 97번 라인으로 해결하였는데 다른환경에서는 틀릴수도 있군요... 많이 배워갑니다, 감사드립니다.

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

문제

문제

출처

ICPC

어디부분에서 틀린지 잘 모르겠습니다. 반례 10만개를 비교해도 안나오네요 ㅠ

qktlf789456 2년 전 0

byeongkeunahn 2년 전 3

qktlf789456 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말