Cod sursa(job #2089111)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 16 decembrie 2017 10:58:03
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
int N;
struct punct
{
    double x,y;
    double dist(punct p)
    {
        return sqrt((this->x-p.x)*(this->x-p.x)+(this->y-p.y)*(this->y-p.y));
    }
    punct(double inx,double iny)
    {
        this->x=inx;
        this->y=iny;
    }
    punct()
    {

    }
}vPuncte[100005];
bool cmp(punct p1,punct p2)
{
    return p1.x<p2.x;
}
bool cmpY(punct p1,punct p2)
{
    return p1.y<p2.y;
}
void citire()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%lf%lf",&vPuncte[i].x,&vPuncte[i].y);
    }
    sort(vPuncte+1,vPuncte+N+1,cmp);
}
double distPeSemiplan(int st,int dr)
{
    if(dr-st==2)
    {
        return min(vPuncte[st].dist(vPuncte[dr-1]),vPuncte[st+1].dist(vPuncte[dr]));
    }
    if(dr-st==1)
    {
        return vPuncte[st].dist(vPuncte[dr]);
    }
    double tmp=min(distPeSemiplan(st,(st+dr)/2),distPeSemiplan((st+dr)/2,dr));
    vector <punct> vAux;
    for(int i=st;i<=dr;i++)
    {
        if(vPuncte[i].dist(punct(vPuncte[(st+dr)/2].x,vPuncte[i].y))<=tmp)
            vAux.push_back(vPuncte[i]);
    }
    sort(vAux.begin(),vAux.end(),cmpY);
    for(int it1=0;it1<4&&it1<vAux.size();it1++)
        for(int it2=4;it2<8&&it2<vAux.size();it2++)
        {
            tmp=min(tmp,vAux[it1].dist(vAux[it2]));
        }
    return tmp;
}
int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    citire();
    printf("%lf",distPeSemiplan(1,N));
    return 0;
}