글 읽기 - 어디서 틀렸는지 도무지 모르겠어요 ㅜㅜ

wjddnjs7895 2년 전 0

이런 저런 예시들 다 집어넣어본 것 같은데 뭐가 틀렸는지 감도 안잡히네요 ㅜㅜ...

차라리 시간초과라면 더 수정해볼텐데 틀렸습니다만 계속 떠서 도무지 뭐가 문제인지...

고수님들 한번만 도와주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
#include <math.h>

using namespace std;

vector<vector<long long>> arr;

long long recur(int left, int right)
{
	if (right - left < 2)
	{
		long long temp = 400000000;
		for (int i = left; i < right; i++)
		{
			for (int j = i + 1; j <= right; j++)
			{
				temp = min(temp, (arr[i][0] - arr[j][0]) * (arr[i][0] - arr[j][0]) + (arr[i][1] - arr[j][1]) * (arr[i][1] - arr[j][1]));
			}
		}
		return temp;
	}
	int mid = (left + right) / 2;
	long long result = min(recur(left, mid), recur(mid + 1, right));

	long long lx = arr[mid][0] - sqrt(result);
	long long rx = arr[mid+1][0] + sqrt(result);

	if (lx < -10000)
		lx = -10000;
	if (rx > 10000)
		rx = 10000;
	int l = 0, r = 0;
	for (int i = left; i <= right; i++)
	{
		if (lx <= arr[i][0])
		{
			l = i;
			break;
		}
	}
	for (int i = right; i >= left; i--)
	{
		if (rx >= arr[i][0])
		{
			r = i;
			break;
		}
	}
	for (int i = l; i < r; i++)
	{
		for (int j = i + 1; j <= r; j++)
		{
			result = min(result, (arr[i][0] - arr[j][0]) * (arr[i][0] - arr[j][0]) + (arr[i][1] - arr[j][1]) * (arr[i][1] - arr[j][1]));
		}
	}
	return result;
}

int main()
{
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		vector<long long> temp;
		long long x, y;
		scanf("%lld %lld", &x, &y);
		temp.push_back(x);
		temp.push_back(y);
		arr.push_back(temp);
	}
	sort(arr.begin(), arr.end());
	printf("%lld\n",recur(0, N - 1));
}

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

문제

문제

출처

ICPC

어디서 틀렸는지 도무지 모르겠어요 ㅜㅜ

wjddnjs7895 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말