알고리즘 과제 PA2

#include <cmath>
#include "closest.h"

#if 0

DO NOT MODIFY closest(void), ~closest(void), and setPoints(point* p, int n)!

#endif

closest::closest(void){
	this->pnt = NULL;
	this->num = 0;
	return;
}

closest::~closest(void){
	if(this->pnt)	delete this->pnt;
	return;
}

void closest::setPoints(point* p, int n){
	int i=0;
	if(this->pnt)	delete this->pnt;
	this->pnt = new point[n];
	this->num = n;
	for(i=0;i<n;i++)	this->pnt[i] = p[i];
	return;
}

double closest::getMinDist(){
	//Input source code her...
	
	return divNcon(0,num);
}

double closest::divNcon(int i, int j){
	int left = i; //맨 왼쪽 점의 인덱스
	int right = j; //맨 오른 쪽 점의 인덱스
	double min=INFINITY;
	if((right-left+1)<=3){ //나눈 결과 점이 3개 이하라면
		for(int t = left; t<right; t++){
			for(int k =t+1; k<=right;k++){
				double dis = sqrt(pow(((pnt+t)->x-(pnt+k)->x),2)+pow(((pnt+t)->y-(pnt+k)->y),2));
				if(min>dis)
					min = dis;
			}
		}
		return min;
	}
	else{
		int mid = (left+right)/2; //중간에 있는 점의 인덱스 (x좌표 위치)
		double leftMin = divNcon(left, mid);
		double rightMin = divNcon(mid+1, right);

		double tmp = 0; //임시 최소거리 tmp 설정
		if(leftMin<rightMin){
			tmp=leftMin;
		}
		else{
			tmp=rightMin;
		}

		double midMin = midClosest(tmp, mid, left, right);
		if(tmp>midMin){
			tmp=midMin;
		}

		return tmp;
	}
}



double closest::midClosest(double d, int mid, int left, int right){
	int index = 0;
	for(int i = left; i<=right;i++){
		if(d>(((pnt+mid)->x)-((pnt+i)->x))&&(((pnt+mid)->x)-((pnt+i)->x))!=0){
			index++;
		}
	}
	int array[index];
	int f=0;
	for(int i = left; i<=right;i++){
		if(d>(((pnt+mid)->x)-((pnt+i)->x))&&(((pnt+mid)->x)-((pnt+i)->x))!=0){
			array[f]=i;
			f++;
		}
	}
	double minum=INFINITY;
	for(int k = 0; k<sizeof(array)/sizeof(array[0]);k++){
		double num = sqrt(pow(((pnt+array[k])->x-(pnt+mid)->x),2)+pow(((pnt+array[k])->y-(pnt+mid)->y),2));
		if(minum>num){
			minum=num;
		}
	}
	return minum;

	//mid를 기준으로 양 옆에 중 가장 짧은 길이 원소 구하는 함수
}