글 읽기 - 반례를 찾아 주실 수 있으신지요!

zellgam 5년 전 0

X축을 기준으로 기준선(소스에서 mid라는 변수)을 잡고 좌우 재귀를 활용하여 최솟값을 구한 뒤, Y을 미리 구한 최솟값을 활용해 최종 최솟값을 구했습니다.

(인터넷에 많이 소개 된 내용)

그런데.. 틀리는데.. 많은 반례를 생각해봤지만 확인이 안되어 이렇게 도움을 요청드립니다.

미리 감사드립니다!

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int n;
vector<pair<int,int>> v, v2;

#define dist(x1, y1, x2, y2) (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)

int Xcompare(const pair<int,int> &p1, const pair<int,int> &p2)
{
	if( p1.first < p2.first )
	{
		return 1;
	}
	else if(  p1.first == p2.first )
	{
		if( p1.second < p2.second )
			return 1;
	}
	return 0;
}
int Ycompare(const pair<int,int> &p1, const pair<int,int> &p2)
{
	if( p1.second < p2.second )
	{
		return 1;
	}
	else if(  p1.second == p2.second )
	{
		if( p1.first < p2.first )
			return 1;
	}
	return 0;
}
int firstStep(int s, int e, int cnt)
{
	if( cnt == 2 )
	{
		return dist(v[s].first, v[s].second, v[e].first, v[e].second);
	}
	if( cnt == 3 )
	{
		int t1 = dist(v[s].first, v[s].second, v[e].first, v[e].second);
		int t2 = dist(v[s].first, v[s].second, v[s+1].first, v[s+1].second);
		int t3 = dist(v[e].first, v[e].second, v[s+1].first, v[s+1].second);
		int m1 = (t1<t2) ? t1:t2 ;
		int m2 = (m1< t3) ? m1:t3 ;
		return m2;
	}

	int mid = (v[cnt/2-1].first + v[cnt/2].first)/2;

	///int mid = n /2;

	
	int d1 = firstStep(s , cnt/2 -1 ,cnt/2  );
	int d2 = firstStep(cnt/2, e, cnt - cnt/2);

	//cout<<"mid: "<<mid<<", d1: "<<d1<<", d2: " <<d2<<endl;
	int d = (d1 < d2) ? d1:d2 ;

	for(int i=0;i<cnt;i++)
	{
		if( abs(v[i].first - mid) < d ) 
			v2.push_back(v[i]);
	}
	
	sort(v2.begin(), v2.end(), Ycompare);
	if( v2.size() > 1 )
	{
		for( auto i =0; i < v2.size() -1 ; i++)
		{
			if( dist(v2[i].first, v2[i].second, v2[i+1].first, v2[i+1].second) < d )
				d = dist(v2[i].first, v2[i].second, v2[i+1].first, v2[i+1].second);
		}
	}
	
	return d;
}

int main(void)
{
	int t1,t2;
	pair<int,int> p;
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		cin>>t1>>t2;
		p = make_pair(t1,t2);
		v.push_back(p);
		
	}

	sort(v.begin(), v.end(), Xcompare);

	v.erase(unique(v.begin(),v.end()),v.end());

	int size = v.size();
	cout << firstStep(0, size-1, size) << endl;


	return 0;
}

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

문제

문제

출처

ICPC

반례를 찾아 주실 수 있으신지요!

zellgam 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말