Cod sursa(job #2015757)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 27 august 2017 14:12:06
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.94 kb
#include <fstream>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#define nmax 100005
using namespace std;
fstream f1("cmap.in", ios::in);
fstream f2("cmap.out", ios::out);
struct punct
{
    double x, y;
}p[nmax], aux,  strip[nmax];
int n, nrpct;
double dist (punct p1, punct p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+ (p1.y-p2.y)*(p1.y-p2.y));
}
void quick(int inf, int sup)
{
  int i, j;
  punct p;
  i = inf;
  j = sup;
  p = strip[(i + j) / 2];
  do
  {
    while ( (i < sup) && (strip[i].x< p.x) ) i++;////cat timp e  ok i<x
    while ( (j > inf) && (strip[j].x> p.x)  )  j--;///cat timp e ok j>x
    if (i<= j)
    {
      aux=strip[i]; strip[i]=strip[j]; strip[j]=aux;
      i++;
      j--;
    }
  } while (i <= j);

  if (inf < j) quick(inf, j);
  if (i < sup) quick(i, sup);
}
double minim(double a, double b)
{
    return (a> b ? b: a);
}
double brute_force(int st, int dr)
{
    if(st==dr) return 0;
    else if(st+1==dr) return dist(p[st], p[dr]);
         else return minim(dist(p[st], p[st+1]), minim(dist(p[st], p[dr]), dist(p[st+1], p[dr]) ));
}
void cre_sort_strip(int st, int dr, int val, double dmin)
{
    int i;//, gap, j;
     nrpct=0;
    for(i=st; i<=dr; i++)
        if(fabs(p[i].x- val)<= dmin) {nrpct++; strip[nrpct]=p[i];}
    /*for(gap=nrpct/2; gap>=1; gap/=2)
        for(i=1+gap; i<=nrpct; i++)
    {
        aux=strip[i];
        for(j=i-gap; (j>=1)&&(strip[j].y> aux.y); j-=gap)
            strip[j+gap]=strip[j];
        strip[j+gap]=aux;
    }*/
    quick(1, nrpct);
}
double dist_strip(double d)
{
    double dis=d, temp;
    int i,j;
    for(i=1; i<nrpct; i++)
        for(j=i+1; j<=nrpct; j++)
    {
        temp=dist(strip[i], strip[j]);
        if(temp< dis) dis=temp;
    }
    return dis;
}
double distmin(int st, int dr)
{
    if(dr-st<=3) return brute_force(st, dr);///reuturnezi minimul pctelor dintre indicii (st, dr)
    else
    {
        double ds, dd, d;
        int mijl=(st+dr)/2;
        ds=distmin(st, mijl);   ///distanta minima a pctelor din stanga liniei x=p[mijl].x
        dd=distmin(mijl+1, dr);  ///distanta minima a pctelor din dreapta liniei x=p[mijl].x
        d=minim(dd, ds);

        cre_sort_strip(st, dr, p[mijl].x,  d); ///vect strip retine pctele la distanta cel mult d de p[mijl], sortate dupa ordonata
        return dist_strip(d); ///dist_strip= dist minima puncte de la stanga dreptei p[mijl] si de la dreapta ei, initializata cu d
    }
}
void citire()///citesti pctele si le sortezi dupa abscisa
{
    int i, gap, j;
    f1>>n;
    for(i=1; i<=n; i++)
        f1>>p[i].x>>p[i].y;
    for(gap=n/2; gap>=1; gap/=2)
        for(i=1+gap; i<=n; i++)
    {
        aux=p[i];
        for(j=i-gap; (j>=1)&&((p[j].x> aux.x)||((p[j].x== aux.x)&&(p[j].y> aux.y))); j-=gap)
            p[j+gap]=p[j];
        p[j+gap]=aux;
    }
}
int main()
{
   citire();
   f2<<fixed<<setprecision(6)<<distmin(1, n);
   return 0;
}