글 읽기 - 반례좀 부탁드립니다..

okonomiyaki 6년 전 0

분할정복으로 풀었는데, 도저히 반례를 못찾겠습니다 흑흑.. ....

Px, Py를 받으면 둘로 나눠서

3개 이하이면 일일이 계산해서 최소길이 리턴하고

그 이상이면 왼쪽 최소(cand1), 오른쪽 최소(cand2)와

나눈 기준선에서부터 x값이 delta = min(cand1, cand2) 안쪽인 점들만 따로 뽑아서

그 점들 서로간 거리중에 최소(cand3)를 찾고,

cand1, cand2, cand3 중에 최소값을 리턴하게 짰는데요

구글링, 텍스트 찾아가며 공부한 알고리즘이라서 구현과정에서 제가 사소한 것을 놓친게 아닌지 생각이 들어요..

반례좀 부탁드립니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdlib>

using namespace std;

class p {
public:
	int x;
	int y;
	int pos = 0; //0 : NULL , 1 : Left , 2 : Right
	p(int _x, int _y) {
		x = _x;
		y = _y;
	}
};

bool compare_x(const p* arg1, const p* arg2)
{
	return arg1->x < arg2->x;
}
bool compare_y(const p* arg1, const p* arg2)
{
	return arg1->y < arg2->y;
}

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

int CP(vector<p*>* Px, vector<p*>* Py) {
	int n = (*Px).size();
	if (n == 2) return dist(*(*Px)[0], *(*Px)[1]);
	else if (n == 3) {
		int min = dist(*(*Px)[0], *(*Px)[1]);
		if (min > dist(*(*Px)[1], *(*Px)[2])) min = dist(*(*Px)[1], *(*Px)[2]);
		if (min > dist(*(*Px)[2], *(*Px)[0])) min = dist(*(*Px)[2], *(*Px)[0]);
		return min;
	}
	vector<p*> Lx, Rx, Ly, Ry;
	for (int i = 0; i < n / 2; i++) {
		Lx.push_back((*Px)[i]);
		(*Px)[i]->pos = 1;
	}
	for (int i = n / 2; i < n; i++) {
		Rx.push_back((*Px)[i]);
		(*Px)[i]->pos = 2;
	}

	for (int i = 0; i < n; i++) {
		if ((*Py)[i]->pos == 1) Ly.push_back((*Py)[i]);
		else if ((*Py)[i]->pos == 2) Ry.push_back((*Py)[i]);
	}

	vector<p*>::iterator itr = Lx.end() - 1;
	int xstar = (*(*itr)).x;
	int cand1 = CP(&Lx, &Ly);
	int cand2 = CP(&Rx, &Ry);
	int delta;
	if (cand1 >= cand2) delta = cand2;
	else delta = cand1;

	vector<p*> S;
	for (int i = 0; i < n; i++) {
		int d = abs(xstar - (*(*Py)[i]).x);
		if (d <= delta) S.push_back((*Py)[i]);
	}
	int cand3 = INT_MAX;
	for (int i = 0; i < (signed int)S.size(); i++) {
		for (int j = 1; j < 16; j++) {
			if (i + j < (signed int)S.size()) {
				if (cand3 > dist(*S[i], *S[i + j])) cand3 = dist(*S[i], *S[i + j]);
			}
		}
	}
	int min = cand1;
	if (min > cand2) min = cand2;
	if (min > cand3) min = cand3;
	return min;
}

int main() {
	vector<p*> Xasc;
	vector<p*> Yasc;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y;
		cin >> x >> y;
		p *point = new p(x, y);
		Xasc.push_back(point);
		Yasc.push_back(point);
	}
	sort(Xasc.begin(), Xasc.end(), compare_x);
	sort(Yasc.begin(), Yasc.end(), compare_y);
	cout << CP(&Xasc, &Yasc) << endl;
	return 0;
}

okonomiyaki 6년 전 0

맞았어요! 진짜 감사드립니다 ㅠㅠ진짜찐짜

이것때문에 일주일동안 애먹었는데 .. 존경스러워요 감사합니당

lch32111 5년 전 0

저도 덕분에 분할정복 문제 푸는데 막혔는데 해결했네요.

geeksforgeeks 사이트 코드를 참고하여 공부했는데,

거기서도 똑같은 오류가 있더라구요.

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

문제

문제

출처

ICPC

반례좀 부탁드립니다..

okonomiyaki 6년 전 0

okonomiyaki 6년 전 0

lch32111 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말