Cod sursa(job #2182245)

Utilizator ioanavasilescuIoana Vasilescu ioanavasilescu Data 22 martie 2018 11:35:15
Problema Cele mai apropiate puncte din plan Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 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];

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<=3)
    {
        double distMin=INT_MAX,dist=0;
        for(int k=0;k<n;k++)
        {
            for(int l=k+1;l<n;l++)
            {
                dist=sqrt((Y[i+k].x-Y[i+l].x)*(Y[i+k].x-Y[i+l].x)+(Y[i+k].y-Y[i+l].y)*(Y[i+k].y-Y[i+l].y));
                if(dist<distMin)distMin=dist;
            }
        }
        return distMin;
    }
    double dist1=cmap(i,n/2),dist2=cmap(i+n/2,n/2);
    double distDiv=min(dist1,dist2);
    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;k++)
        {
            dist=sqrt((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",distMin);
    return 0;
}