글 읽기 - 틀렸습니다의 반례를 찾습니다.

rmstjd23 2년 전 0

구현은 세그먼트 트리를 이용했습니다.

input 함수에서 입력을 x축, y축으로 정렬하고 중복점 제거하고

세그먼트 트리를 만들때, 좌우 영역을 가로지르는 선분에 대한 계산을 getMinDistance 함수에서 처리하였습니다.

8%에서 오답 처리가 되는데 반례 또는 제가 놓친 부분을 알려주실수 있는 친절하신 분이 계실까요?

#include <iostream>
#include <vector>
#include <cmath>
#include <limits.h>
#include <algorithm>

using namespace std;

struct point2D {
	int x;
	int y;

	bool operator==(point2D target)
	{
		return x == target.x && y == target.y;
	}
};

bool sortRule(point2D first, point2D second)
{
	if (first.x == second.x)
		return first.y < second.y;

	return first.x < second.x;
};

int distance(point2D first, point2D second)
{
	return (first.x - second.x) * (first.x - second.x) + (first.y - second.y) * (first.y - second.y);
}

vector<point2D> input()
{
	int pointCount;
	vector<point2D> ret;
	cin >> pointCount;

	for (int i = 0; i < pointCount; i++)
	{
		point2D temp;
		cin >> temp.x >> temp.y;

		ret.push_back(temp);
	}

	sort(ret.begin(), ret.end(), sortRule);
	ret.erase(unique(ret.begin(), ret.end()), ret.end());

	return ret;
}


int getMinDistance(vector<point2D>& points, int start, int end, int min)
{
	if (start > points.size() - 1)
		return min;
	int mid = (start + end) / 2;

	if (mid > points.size() - 2)
		return min;
	if (end > points.size() - 1)
		end = points.size() - 1;
	int ret = min;

	double centor = (points[mid].x + points[mid + 1].x) / 2;

	for (int i = mid; i >= start; i--)
	{
		if (pow(points[i].x - centor, 2) >= ret)
			break;

		for (int j = mid + 1; j <= end; j++)
		{
			if (pow(points[j].x - centor, 2) >= ret)
				break;

			auto dist = distance(points[i], points[j]);
			if (ret > dist)
				ret = dist;
		}
	}

	return ret;
}

int makeSegmentTree(vector<int>& tree, vector<point2D>& points, int cur)
{
	if (cur * 2 < tree.size())
	{
		int start, end, min;
		int treeDepth = log2(tree.size() / 2);
		int curDepth = log2(cur);

		start = cur * pow(2, (treeDepth - curDepth)) - (tree.size() / 2);
		end = (cur + 1) * pow(2, (treeDepth - curDepth)) - 1 - (tree.size() / 2);

        
		auto left = makeSegmentTree(tree, points, cur * 2);
		min = left;

		auto right = makeSegmentTree(tree, points, cur * 2 + 1);
		min = min < right ? min : right;

		int mid = getMinDistance(points, start, end, min);
		min = min < mid ? min : mid;

		tree[cur] = min;
	}

	return tree[cur];
}

vector<int> getSegmentTree(vector<point2D>& points)
{
	int treeSize = pow(2, ceil(log2(points.size())));
	vector<int> ret(treeSize * 2, INT_MAX);

	makeSegmentTree(ret, points, 1);

	return ret;
}

int main()
{
	auto pointList = input();
	auto tree = getSegmentTree(pointList);

	cout << tree[1] << endl;

	return 0;
}

ksoosung77 2년 전 1

'여러 점이 같은 좌표를 가질 수도 있다.'

반례입니다.

4
0 0
10000 10000
-10000 -10000
0 0

출력값:

200000000

실제 값:

rmstjd23 2년 전 0

좌표가 같은 다른 두 점을 같은 점 이라고 생각한게 실수였네요

해결했습니다 감사합니다.

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

문제

문제

출처

ICPC

틀렸습니다의 반례를 찾습니다.

rmstjd23 2년 전 0

ksoosung77 2년 전 1

rmstjd23 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말