Cod sursa(job #2050970)

Utilizator VladLujerdeanuVlad Lujerdeanu VladLujerdeanu Data 28 octombrie 2017 13:11:47
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;
ifstream fs("cmap.in");
ofstream of("cmap.out");
struct punct{
	int x;
	int y;
} ;
vector<punct> pcts;
vector<punct> pctsy;
void sort_by_x(){
	sort(pcts.begin(),pcts.end(),[](const punct& p1,const punct& p2){return p1.x<p2.x;});
}
int euclid(const punct& p1,const punct p2){
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
int interclasare(int st,int mij, int dr){
	vector<punct> vst;
	vector<punct> vdr;
	copy(pctsy.begin()+st,pctsy.begin()+mij,back_inserter(vst));
	copy(pctsy.begin()+mij+1,pctsy.begin()+dr,back_inserter(vdr));
	int i=0,j=0;
	auto curent_st = vst.begin();
	auto curent_dr = vdr.begin();
	auto curent =pctsy.begin()+st;
	while(curent_st!=vst.end() && curent_dr!=vdr.end()){
		if ((*curent_st).y<(*curent_dr).y)
		{
			(*curent)=(*curent_st);
			curent_st++;
		}else{
			(*curent)=(*curent_dr);
			curent_dr++;
		}
		curent++;
		
	}
	while (curent_st!=vst.end()){
		(*curent)=(*curent_st);
			curent_st++;
	}
	
	while (curent_dr!=vdr.end()){
		(*curent)=(*curent_dr);
			curent_dr++;
	}
}
int puncte_apropiate(int st, int dr, punct& p1,punct& p2){
	int mij = (st+dr)/2;
	if (dr-st==1){
		p1 = pcts[st];
		p2 = pcts[dr];
		if (p1.y>p2.y)
			swap(p1,p2);
		return euclid(pcts[st],pcts[dr]);
	}
	if (dr-st==2){
		int l1 =euclid(pcts[st],pcts[st+1]);
		int l2 =euclid(pcts[st+1],pcts[dr]);
		int l3 =euclid(pcts[st],pcts[dr]);
		
		if (l1<l2 && l1<l3){
				p1 = pcts[st];
				p2 = pcts[st+1];
				return l1;
		}
		if (l2<l1 && l2<l3){
				p1 = pcts[st];
				p2 = pcts[st+1];
				return l2;
		}
		if (l3<l1 && l3<l2){
				p1 = pcts[st];
				p2 = pcts[st+1];
				return l3;
		}		
		sort(pcts.begin()+st,pcts.begin()+dr,[](const punct& p1,const punct& p2){return p1.y<p2.y;});
	}
	punct bs1,bs2,bd1,bd2;
	int best_s = puncte_apropiate(st,mij,bs1,bs2);
	int best_d = puncte_apropiate(mij+1,dr,bd1,bd2);
	int best;
	if (best_s<best_d)
	{
		p1 = bs1;
		p2 = bs2;
		best = best_s;
	}else
	{
		p1 = bd1;
		p2 = bd2;
		best = best_d;
	}
	interclasare(st,mij,dr);
	for (int i=st;i<=dr;i++){
	for(int j=1;j<=7;j++){
			if ((i+j)<=dr){
				int cbest = euclid(pctsy[i],pctsy[i+j]);
				if (cbest<best){
					p1 =pctsy[i];
					p2 =pctsy[j];
					best=cbest; 
				}
			}
		}
	}
	return min(best_s,best_d);
}
int main(){
int nr_puncte;
fs>>nr_puncte;
for (int i=0;i<nr_puncte;i++){
	punct p;
	fs>>p.x>>p.y;
	pcts.push_back(p);
	pctsy.push_back(p);
}
sort_by_x();
punct p1,p2;
int r = puncte_apropiate(0,nr_puncte-1,p1,p2);
of<<setprecision(8)<<sqrt(r);
return 0;
}