글 읽기 - 가장 가까운 두 점 찾기... 뭐가 틀린걸까요?

gkfkagkfka12 5년 전 0

x좌표 정렬 -> 컷팅 -> y좌표 정렬 -> 컷팅 -> 정답얻어냄

다른 사람들과 동일한 방식인데 어떤 부분이 틀렸는지 모르겠습니다 ㅠㅠ

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct Point {
	int x;
	int y;
};
vector<Point> coor;

int dist(const Point &p1, const Point &p2)
{
	return (p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y);
}

bool cmp(const Point &p1, const Point &p2) {
	return p1.x < p2.x;
}

bool cmp2(const Point &p1, const Point &p2) {
	return p1.y < p2.y;
}

int closest(int s1, int s2)
{
	if (s1 == s2 - 1) return dist(coor[s1], coor[s2]);
	if (s1 == s2 - 2) return min(dist(coor[s1], coor[s1 + 1]), 
		min(dist(coor[s1 + 1], coor[s2]), dist(coor[s1], coor[s2])));
	int mid = (s1 + s2) / 2;
	int left = closest(s1, mid);
	int right = closest(mid + 1, s2);

	int d = min(left, right);

	vector<Point> candidate;
	for (int i = s1; i <= s2; i++) {
		int diff = coor[mid].x - coor[i].x;
		if (diff*diff <= d)
			candidate.push_back(coor[i]);
	}

	sort(candidate.begin(), candidate.end(), cmp2);
	
	for (size_t i = 0; i < candidate.size() - 1; i++) {
		for (size_t j = i + 1; j < candidate.size(); j++) {
			int diff = coor[i].y - coor[j].y;
			if (diff*diff <= d)
				d = min(d, dist(coor[i], coor[j]));
			else
				break;
		}
	}
	return d;
}


int main(void)
{
	int n;
	scanf("%d", &n);
	coor.resize(n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &coor[i].x, &coor[i].y);
	}

	// x좌표 기준으로 정렬
	sort(coor.begin(), coor.end(), cmp);

	printf("%d\n", closest(0, n-1));
	return 0;
}

gkfkagkfka12 5년 전 0

감사합니다. 그런데 여전히 시간초과가 발생하네요 ㅠㅠ

gkfkagkfka12 5년 전 1

풀었습니다~ candidate 검사할 때 diff*diff<=d가 아니라 diff*diff<d로 바꿔줘야 되네용

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

문제

문제

출처

ICPC

가장 가까운 두 점 찾기... 뭐가 틀린걸까요?

gkfkagkfka12 5년 전 0

gkfkagkfka12 5년 전 0

gkfkagkfka12 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말