글 읽기 - 왜 틀렸을까용? ㅠㅠ

powerlsj7 2년 전 0

물론 잘못 짜있는 코드라 통과가 안된거겠지만.. 원인을 모르니 ㅠㅠ

반례도 잘 통과하는데 ㅠㅠ

요고는 잘 통과해용

50
31 50
38 76
20 53
29 47
-77 87
-72 -89
-1 -38
40 -36
47 -1
67 -27
-20 70
99 33
-13 66
-55 -65
-39 36
55 33
31 -54
-13 -84
55 81
-24 96
3 1
-57 -68
45 -15
43 51
62 -52
52 15
50 -79
18 -21
42 -11
0 -89
54 -93
-5 10
91 78
41 8
69 40
37 -77
-58 -57
62 28
24 -70
-39 -33
-32 87
-63 -70
-29 -27
-36 18
-56 -11
-19 -68
-75 51
-27 -79
81 30
-25 -98

% What was actually got
12

% What was expected
13

#include<iostream>
#include<algorithm>
using namespace std;
int n;
pair<int, int> xy[100001];
int GetDistance(int left, int right)
{
	int xx = xy[left].first - xy[right].first;
	int yy = xy[left].second - xy[right].second;

	return xx * xx + yy * yy;
}
bool cmp(pair<int,int> a, pair<int,int> b)
{
	if (abs(a.first) < abs(b.first))
	{
		return true;
	}
	else if (abs(a.first) > abs(b.first))
	{
		return false;
	}
	else
	{
		if (abs(a.second) < abs(b.second))
		{
			return true;
		}
		else if (abs(a.second) > abs(b.second))
		{
			return false;
		}
	}
	return false;
}
int GetResult(int left,int right)//가장 가까운 두점을 구한다.
{
	int mid = (left + right) / 2;
	if (right - left == 2)
	{
		int min = 1000000000;
		for (int i = left; i <= right; i++)
		{
			for (int j = left; j <= right; j++)
			{
				if (i == j)
				{
					continue;
				}
				int xx = xy[i].first - xy[j].first;
				int yy = xy[i].second - xy[j].second;
				if (min > xx * xx + yy * yy)
				{
					min = xx * xx + yy * yy;
				}
			}
		}
		return min;
	}
	if (right - left == 1)
	{
		int xx = xy[left].first - xy[right].first;
		int yy = xy[left].second - xy[right].second;
		
		return xx * xx + yy * yy;
	}
	int result= min(GetResult(left,mid), GetResult(mid, right));
	for (int i = mid+1; i < right; i++)
	{
		int d= GetDistance(mid, i);
		if (result < d)
		{
			break;
		}
		if (d < result)
		{
			result=d;
		}
	}
	for (int i = mid - 1; i >= left; i--)
	{
		int d = GetDistance(mid, i);
		if (result < d)
		{
			break;
		}
		if (d < result)
		{
			 result=d;
		}
	}
	return result;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> xy[i].first;
		cin >> xy[i].second;
	}
	sort(xy+1, xy + n, cmp);
	cout<<GetResult(1, n);
	return 0;
}

bamgoesn 2년 전 1

테스트케이스 드립니다.

4
1 2
1 0
0 2
0 1

정답: 1
출력: 2

(아래는 순서만 다름)
4
0 1
0 2
1 0
1 2

정답: 1
출력: 1

powerlsj7 2년 전 0

윽.. 도움주신 반례로 했는데 오류 부분이

정렬이 제대로 안된 것 같더라고용.

sort의 범위가 arr+1 부터라 arr+1+n으로 수정해서 정렬이 완료되고

첫 번째 케이스

4
1 2
1 0
0 2
0 1

1이 나오는데요.

ㅠㅠ 채점돌리면 틀리네용.히히 ..ㅠㅠ

powerlsj7 2년 전 0

오늘 반례

-5 0

-3 4

2 1

3 4

-1 1

8 8

1 7

답: 9

요고로 하니까 25가 나오길래 문제점을 찾다가. 코드를 수정했는데 저는 mid에서 오른쪽 왼쪽으로 탐색하면서 abs(타겟y-midy) 를 거리가 갱신될 때 저장하고 다음 순서의 점이 y가 더 높은 곳에 위치하면 아예 탐색 중지하는 식으로 구현했는데 이방법이 틀린걸까요?

#include<iostream>
#include<algorithm>
using namespace std;
int n;
pair<int, int> xy[100001];
int GetDistance(int left, int right)
{
	int xx = xy[left].first - xy[right].first;
	int yy = xy[left].second - xy[right].second;

	return xx * xx + yy * yy;
}
bool cmp(pair<int,int> a, pair<int,int> b)
{
	if (a.first < b.first)
	{
		return true;
	}
	else if (a.first > b.first)
	{
		return false;
	}
	else
	{
		if (a.second < b.second)
		{
			return true;
		}
		else if (a.second >b.second)
		{
			return false;
		}
	}
	return false;
}
int GetResult(int left,int right)//가장 가까운 두점을 구한다.
{
	int mid = (left + right) / 2;
	if (right - left == 2)
	{
		int minV= 2000000000;
		for (int i = left; i <= right; i++)
		{
			for (int j = left; j <= right; j++)
			{
				if (i == j)
				{
					continue;
				}
				int xx = xy[i].first - xy[j].first;
				int yy = xy[i].second - xy[j].second;
				if (minV > xx * xx + yy * yy)
				{
					minV = xx * xx + yy * yy;
				}
			}
		}
		return minV;
	}
	if (right - left == 1)
	{
		int xx = xy[left].first - xy[right].first;
		int yy = xy[left].second - xy[right].second;
		
		return xx * xx + yy * yy;
	}
	int result= min(GetResult(left,mid), GetResult(mid, right));
	int y = 2000000000; //여기서 y로 저장해서 비교하는 부분 for문 2번
	for (int i = mid+1; i <= n; i++)
	{
		int d= GetDistance(mid, i);
		if (y < abs(xy[mid].second-xy[i].second))
		{
			break;
		}
		if (d < result)
		{
			result=d;
			y = abs(xy[mid].second - xy[i].second);
		}
	}
	y = 2000000000;
	for (int i = mid - 1; i >= 1; i--)
	{
		int d = GetDistance(mid, i);
		if (y < abs(xy[mid].second - xy[i].second))
		{
			break;
		}
		if (d < result)
		{
			result = d;
			y = abs(xy[mid].second - xy[i].second);
		}
	}
	return result;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> xy[i].first;
		cin >> xy[i].second;
	}
	sort(xy+1, xy + n+1, cmp);
	cout<<GetResult(1, n);
	return 0;
}

some256 2년 전 2

가장 최근 소스코드의 반례입니다.

% Input
9
43 51
62 -52
52 15
50 -79
18 -21
42 -11
0 -89
54 -93
-5 10

% What was actually got
676

% What was expected
212


iteration = 7

powerlsj7 2년 전 0

감사합니다. 이제 마지막 반례까지 통과하는데 시간초과가 걸리네용. 범위를 x좌표 거리로만 제한을 거는데 다른 생각해볼 사항이 있을까용? ㅠ

some256 2년 전 0

시간초과인 경우 GetDistance()를 잘 사용하고 있는지 확인해보세요. GetDistance()는 거리의 제곱을 반환하는데 실제로 필요한 건 거리의 제곱이 아닌 거리이므로 거리의 제곱을 사용하면 범위가 잘 줄지 않을 수 있습니다.

powerlsj7 2년 전 0

댓글 달아주신 분들 감사드립니다. 이 문제는 많이 공부한 것 같습니다.

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

문제

문제

출처

ICPC

왜 틀렸을까용? ㅠㅠ

powerlsj7 2년 전 0

bamgoesn 2년 전 1

powerlsj7 2년 전 0

powerlsj7 2년 전 0

some256 2년 전 2

powerlsj7 2년 전 0

some256 2년 전 0

powerlsj7 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말