글 읽기 - 2261번 분할정복 질문드립니다..

adh30 4년 전 0

2261번 가장 가까운 두 점 문제를 풀지 못하여, 인터넷의 분할정복 코드를 참조하였는데 어디서 틀린건지 잘 모르겠습니다..ㅠㅠ

아래와 같이 풀었습니다.

1. x축 기준으로 정렬합니다.

2. 분할선을 기준으로 좌, 우 에서 거리의 최솟값을 찾습니다.

3. 분할선과의 x좌표의 차가 위에서 구한 거리보다 작은 점들을 벡터에 담습니다.

4. 해당 벡터를 y축을 기준으로 정렬합니다.

5. y좌표간의 차가 위에서 구한 거리보다 작은 점들끼리 거리를 계산하여 답을 찾습니다.

혹시 틀린 케이스가 어떤 것인지, 왜인지 알려주실 수 있으실까요. 감사합니다.

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

struct Point {
	int x;
	int y;
};

vector<Point> v;
bool compare(Point p1, Point p2) {
	return p1.x < p2.x;
}

bool sortY(Point p1, Point p2) {
	return p1.y < p2.y;
}
int dist(Point p1, Point p2) {
	return pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2);
}
int divide(int start, int end) {
	if (end - start + 1 <= 3) { // 길이가 짧다면 brute force로 거리 계산
		int tmp = 99999;
		for (int i = start; i < end; i++) {
			for (int j = i + 1; j <= end; j++) {
				tmp = min(tmp,dist(v[i], v[j]));
			}
		}
		return tmp;
	}
	int mid = (start + end) / 2;
	int tmpAns = min(divide(start, mid), divide(mid + 1, end));
	vector<Point> yVec;

	for (int i = start; i <= end; i++) {//x간의 차가 min거리보다 작은것들 push
		int d = v[i].x - v[mid].x;
		if (d * d < tmpAns) {
			yVec.push_back(v[i]);
		}
	}
	sort(yVec.begin(), yVec.end(), sortY); // y축 정렬

	int len = (int)yVec.size();
	for (int i = 0; i < len-1; i++) {
		for (int j = i + 1; j < len; j++) {
			int d = v[j].y - v[i].y;
			if (d * d < tmpAns) {// y간의 차가 min거리보다 짧다면
				// 걔네 계산
				tmpAns = min(tmpAns, dist(v[i], v[j]));
			}
			else {
				break;
			}
		}
	}
	return tmpAns;
}

int main() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		v.push_back({ x,y });
	}
	sort(v.begin(), v.end(), compare);
	cout<<divide(0, N - 1)<<endl;
}

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

문제

문제

출처

ICPC

2261번 분할정복 질문드립니다..

adh30 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말