글 읽기 - 이 방법이 왜 잘못됐는지 궁금합니다

gunwooyeon 6년 전 0

분할 정복을 통하여 mid 양 사이드 최소 길이를 구하고,

mid가 처리가 되지 않았기 때문에, 전체 배열을 돌며, mid 인덱스를 제외하고 길이를 구하여 분할정복에서 구한 ans와 비교하여

최솟값을 답으로 출력하게 했는데, 왜 틀린지 알고 싶습니다.

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

struct Point {
	int x, y;
	Point() {
	}
	Point(int x, int y) : x(x), y(y) {
	}
	bool operator < (const Point &v) const {
		if (x == v.x) {
			return y < v.y;
		}
		else {
			return x < v.x;
		}
	}
};

bool cmp(const Point &u, const Point &v) {
	return u.y < v.y;
}

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

int brute_force(vector<Point> &a, int x, int y) {
	int ans = -1;
	for (int i = x; i <= y - 1; i++) {
		for (int j = i + 1; j <= y; j++) {
			int d = dist(a[i], a[j]);
			if (ans == -1 || ans > d) {
				ans = d;
			}
		}
	}
	return ans;
}

int closest(vector<Point> &a, int x, int y) {
	int n = y - x + 1;
	if (n <= 3) {
		return brute_force(a, x, y);
	}
	int mid = (x + y) / 2;
	int left = closest(a, x, mid);
	int right = closest(a, mid + 1, y);
	int ans = min(left, right);
	for (int i = x; i <= y; i++) {
		if (i == mid) continue;
		int d = (a[i].x - a[mid].x) * (a[i].x - a[mid].x)
			+ (a[i].y - a[mid].y) * (a[i].y - a[mid].y);
		if (d < ans) {
			ans = d;
		}
	}
	return ans;
}

int main() {
	int n;
	scanf("%d", &n);
	vector<Point> a(n);
	for (int i = 0; i<n; i++) {
		scanf("%d %d", &a[i].x, &a[i].y);
	}
	sort(a.begin(), a.end());
	printf("%d\n", closest(a, 0, n - 1));
    
	return 0;
}

chogahui05 6년 전 0

point x ~ point y까지의 점 쌍 중에서 최단 거리를 가지는 쌍 (a,b)를 찾으세요 할 때..

mid점을 하나 뒀네요. (x~mid) (mid+1,y)

일단 x~mid까지 최단 점쌍 + mid+1 ~ y까지 최단 점쌍 구해서 최소치 구하는 것까진 맞습니다.

한 친구는 (x~mid) 중에 하나에 포함되고, 다른 친구가 (mid+1 ~ y)에 포함된다고 쳤을 때

이런 조건을 만족하는 점쌍 중에서

mid, uu (단 uu는 mid+1 ~ y사이에 있는 점 중 하나)가 최단 거리 점쌍이 된다는 보장이 있나요?

예를 들어서, 이런 경우를 생각해 봅시다.

1 1 <== x

1 3

1 5

1 1000000 <== mid

2 2

2 3

2 4 <== y

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

문제

문제

출처

ICPC

이 방법이 왜 잘못됐는지 궁금합니다

gunwooyeon 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말