Pagini recente » Cod sursa (job #2064835) | Cod sursa (job #1052032) | Cod sursa (job #2952882) | Cod sursa (job #1454287) | Cod sursa (job #2050970)
#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;
}