Cod sursa(job #2182274)

Utilizator ioanavasilescuIoana Vasilescu ioanavasilescu Data 22 martie 2018 11:52:52
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <limits.h>

#define lim 100010

using namespace std;

ifstream fin("cmap.in");
FILE *f=fopen("cmap.out","w");

//double maxLength;
int nFirst;

struct punct
{
    int x,y;
}Y[lim],Z[lim];


bool sortConditionX(punct i,punct j)
{
    if(i.x<j.x) return 1;
    if(i.x==j.x && i.y<j.y) return 1;
    return 0;
}

bool sortConditionY(punct i,punct j)
{
    if(i.y<j.y) return 1;
    if(i.y==j.y && i.x<j.x) return 1;
    return 0;
}

void check(int n)
{
    for(int i=1;i<=n;i++)
        cout<<Y[i].x<<" "<<Y[i].y<<"\n";
    cout<<"\n";
}

double cmap(int i,int n)
{
    if(n==1)
    {
        return INT_MAX;
    }
    if(n==2)
    {
        if(Y[i].y>Y[i+1].y)
        {
            punct aux;
            aux=Y[i];
            Y[i]=Y[i+1];
            Y[i+1]=aux;

        }
        return (Y[i].x-Y[i+1].x)*(Y[i].x-Y[i+1].x)+(Y[i].y-Y[i+1].y)*(Y[i].y-Y[i+1].y);
    }
    double dist1=cmap(i,n/2),dist2=cmap(i+n/2,n/2);
    double distDiv=min(dist1,dist2);
    merge(Y+i,Y+i+n/2,Y+i+n/2,Y+i+n,Z+i,sortConditionY);
    int zs=n/2,zd=n/2;
    while(zs>=1 && Y[n/2].x-Y[zs].x<=distDiv)
        zs--;
    while(zd<=nFirst && Y[zd].x-Y[n/2].x<=distDiv)
        zd++;
    ///sort(Y+zs,Y+zd+1,sortConditionY);
    for(int i=zs;i<=zd;i++)
    {
        double dist=0;
        for(int k=1;k<8 && i+k<=zd;k++)
        {
            dist=(Y[i+k].x-Y[i].x)*(Y[i+k].x-Y[i].x)+(Y[i+k].y-Y[i].y)*(Y[i+k].y-Y[i].y);
            if(dist<distDiv)distDiv=dist;
        }
    }
    return distDiv;
}

int main()
{
    int xmax=0,ymax=0;
    fin>>nFirst;
    for(int i=1;i<=nFirst;i++)
    {
        fin>>Y[i].x>>Y[i].y;
        /*if(Y[i].x>xmax)xmax=Y[i].x;
        if(Y[i].y>ymax)ymax=Y[i].y;*/
    }
    check(nFirst);
    sort(Y,Y+nFirst,sortConditionX);
    check(nFirst);
    //maxLength=sqrt(xmax*xmax+ymax*ymax);
    double distMin=cmap(1,nFirst);
    fprintf(f,"%f",sqrt(distMin));
    return 0;
}