글 읽기 - 어떤부분이 잘못된걸까요 ?? ㅜㅜ도와주세요

isvara 4년 전 0

우선 구현은

x를 기준으로 우선정렬하고 같은 x끼리 묶어내도록 group을 만들었습니다.

그리고 나서 i 의 i+1번째 점과 비교한 점과 현재 i와 그다음 group의 최단거리를 lower_bound로 구해내서 i와 가장 가까운 점을 구현하도록 해서

순회하도록 구현했습니다.

혹시 반례나 코드상 잘못된부분이 있을까요 ㅜ??

그리고 게시판을 보니까 분할정복으로 푸시는 분들이 계신데 어떠한 방식으로 분할정복이 적용되어야 할까요??

#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;

int N;
double ans = 987654321;
vector<pair<ll, ll>>p[100001];
pair<ll, ll> tmp[100001];
bool comp(pair<ll, ll>p1, pair<ll, ll>p2) {
	if (p1.first < p2.first)
		return true;
	else if (p1.first > p2.first)
		return false;
	else {
		if (p1.second < p2.second)
			return true;
		else if (p1.second > p2.second)
			return false;
	}
}
double dist(pair<ll, ll>p1, pair<ll, ll>p2) {
	ll x = abs(p1.first - p2.first);
	ll y = abs(p1.second - p2.second);

	ll re = x * x + y * y;
	return sqrt(re);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++)cin >> tmp[i].first >> tmp[i].second;

	sort(tmp + 1, tmp + N + 1, comp);
	int cur = tmp[1].first;
	int index = 1;
	p[1].push_back(tmp[1]);

	for (int i = 2; i <= N; i++) {
		if (cur == tmp[i].first)
			p[index].push_back(tmp[i]);
		else {
			p[++index].push_back(tmp[i]);
			cur = tmp[i].first;
		}
	}

	for (int i = 1; i < index; i++) {
		for (int j = 0; j < (int)p[i].size(); j++) {//다음 group 중 y가 가장 가까운 점
			vector<pair<ll, ll>>::iterator it = lower_bound(p[i + 1].begin(), p[i + 1].end(), p[i][j]);

			if (it == p[i + 1].begin())
				ans = min(ans, dist(p[i][j], p[i + 1][0]));
			else {
				ans = min(ans, dist(p[i][j], (*it)));
				ans = min(ans, dist(p[i][j], *(--it)));
			}
		}

		for (int j = 0; j < (int)p[i].size() - 1; j++)//마지막은 제외하고 모든 그룹의 next또한 최단정점이 될 수 있음
			ans = min(ans, dist(p[i][j], p[i][j + 1]));
	}

	for (int k = 0; k < p[index].size() - 1; k++) {
		ans = min(ans, dist(p[index][k], p[index][k + 1]));
	}
	cout << ans * ans;
}

oree2113 4년 전 3

가장 가까운 두 점의 x 좌표가 연속하지 않을 수도 있습니다.

4
1 0
2 -10
3 10
4 0
// ans : 9
// output : 101

isvara 4년 전 0

아..그러한 사례가 있었군요 ㅜ... 라인스위핑으로 해결하는 풀이를 보긴했는데 이해가 아직은 잘안가내요 답변감사합니다.

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

문제

문제

출처

ICPC

어떤부분이 잘못된걸까요 ?? ㅜㅜ도와주세요

isvara 4년 전 0

oree2113 4년 전 3

isvara 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말