글 읽기 - closest pair 코드 어느 부분이 잘못 된걸까요?

seastar105 4년 전 0

분할정복으로 풀려고 했습니다.

최근접점을 구해야하는 점의 수가 적으면 브루트포스로 구하고 아니면 분할하는 방식입니다. 입력을 받고나면 일단 x좌표를 기준으로 정렬했습니다.

반으로 분할 해서 오른쪽 왼쪽에서 가장 가까운 거리를 구하고, 둘 중에 더 작은 값을 m으로 놓습니다. 중간부분을 보기 위해서 왼쪽 마지막 값보다 작은 애들중에 d보다 적게 작은애들, 오른쪽 가장 작은 값보다 d보다 적게 큰 애들을 middle에 넣고 middle을 y좌표 기준으로 정렬한 다음에 이 middle 안에서 가장 가까운 쌍을 찾습니다.

이런 생각으로 짠 건데 계속 틀리네여 도와주세여

#include<bits/stdc++.h>

using namespace std;

struct Point{
	int x,y;
	Point(int a, int b) : x(a), y(b) {};
	Point() : x(0), y(0) {};
};

int N;
vector<Point> points(100005);
int thr = 16;

int dist(Point &a, Point &b) {
	return (a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y);
}

bool cmp(Point &a, Point &b) {
	return a.x < b.x;
}

bool cmp2(Point &a, Point &b) {
	return a.y < b.y;
}

double solve(int left, int right) {
	if(right - left + 1 <= thr) {
		int minimum = INT_MAX;
		for(int i=left;i<right;++i) {
			for(int j=i+1;j<=right;++j) {
				int tmp = dist(points[i], points[j]);
				if(minimum > tmp) minimum = tmp;
			}
		}
		return minimum;
	}
	int mid = (right + left) / 2;
	int m = min(solve(left, mid), solve(mid+1, right));
	vector<Point> middle;
	for(int i=mid;i>=left;--i) {
		int tmp = points[i].x- points[mid].x;
		if(tmp * tmp >= m) break;
		middle.push_back(points[i]);
	}
	for(int i=mid+1;i<=right;++i) {
		int tmp = points[i].x - points[mid+1].x;
		if(tmp * tmp >= m) break;
		middle.push_back(points[i]);
	}
	sort(middle.begin(), middle.end(), cmp2);
	int n = middle.size();
	for(int i=0;i<n-1;++i) {
		for(int j=i+1;j<n;++j) {
			int tmp = middle[j].y - middle[i].y;
			if(tmp * tmp >= m) break;
			m = min(m, dist(middle[i], middle[j]));
		}
	}
	return m;
}

int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> N;
	for(int i=0;i<N;++i) cin >> points[i].x >> points[i].y;
	sort(points.begin(), points.begin()+N, cmp);
	cout << solve(0,N-1) << '\n';
	return 0;
}

seastar105 4년 전 0

Point 구조체 좌표를 long long으로 바꾸고 거리 계산도 long long으로 전부 바꾸니까 이 코드 통과하는 거 같네여 이거로 하루죙일 고민했는데 해결되서 다행이에여

seastar105 4년 전 0

헉 아니네 solve 반환값을 int로만 바꿔도 통과하네영

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

문제

문제

출처

ICPC

closest pair 코드 어느 부분이 잘못 된걸까요?

seastar105 4년 전 0

seastar105 4년 전 0

seastar105 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말