Cod sursa(job #1017967)

Utilizator jul123Iulia Duta jul123 Data 28 octombrie 2013 18:46:41
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.72 kb
#include<iostream>
#include<fstream>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<iomanip>
typedef struct punct{
long long x;
long long y;
}P;
P v[100000],tmp, pct[100000];
int n;
using namespace std;
long long pivot(int left, int right)
{
    long long  p1,p2,p3,p,mini,maxi;
    p1=v[left + rand() % (right-left+1)].x;
    p2=v[left + rand() % (right-left+1)].x;
    p3=v[left + rand() % (right-left+1)].x;
    if(p1<=p2&&p1<=p3)
        mini=p1;
    if(p2<=p1&&p2<=p3)
        mini=p2;
    if(p3<=p1&&p3<=p2)
        mini=p3;
    if(p1>=p2&&p1>=p3)
        maxi=p1;
    if(p2>=p1&&p2>=p3)
        maxi=p2;
    if(p3>=p1&&p3>=p2)
        maxi=p3;
    p=p1+p2+p3-maxi-mini;
    return p;

}
 long long dist(P va[], int a, int b)
{
    return ((va[b].x-va[a].x)*(va[b].x-va[a].x)+(va[b].y-va[a].y)*(va[b].y-va[a].y));
}
void quicksort( int left, int right)
{
    int i=left, j=right;
    long long piv, tmpo;
    piv=pivot(left,right);
    while(i<=j)
    {
        while(v[i].x<piv)
            i++;
        while(v[j].x>piv)
            j--;
        if(i<=j)
        {
            tmp=v[i];
            v[i]=v[j];
            v[j]=tmp;
            if(v[i].x==v[j].x)
            if(v[i].y>v[j].y){
                tmpo=v[i].y;
                v[i].y=v[j].y;
                v[j].y=tmpo;
            }

            i++;
            j--;
        }
    }
    if(left<j)
        quicksort(left,j);
    if(i<right)
        quicksort(i,right);

}

long long cmap(int left, int right)
{
    long long a1, d, nr, nr1, nr2;
    int t, k, a, b, c, mij, i, j;
    if(left<=right)
    {
    if(left==right)
        return 1000000;
    if(right-left==1)
        return dist(pct, left, right);
    else if(right-left==2)
    {
        a=left;
        b=left+1;
        c=left+2;
        nr=min(dist(pct, a,b),dist(pct, a,c));
        nr=min(nr, dist(pct, b,c));
        return nr;
    }
    else{

        k=0;
        mij=(left+right)/2;
        nr1=cmap(left, mij);
        nr2=cmap(mij, right);
        nr=min(nr1,nr2);
        for(i=0;i<n;i++){
            if((abs(pct[i].x-pct[mij].x))<nr)
                {v[k].x=pct[i].y;
                v[k].y=pct[i].x;
                k++;}
        }
        quicksort(0, k-1);
        for(i=0;i<k;i++)
           for(j=1;j<8;j++)
        {
                if(i+j<k)
                d=dist(v, i,i+j);
                if(d<nr)
                    nr=d;

        }


}
    }
return nr;

}
int main()
{
    int  i;
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    f>>n;
    for(i=0;i<n;i++)
        f>>pct[i].x>>pct[i].y;
    quicksort(0,n-1);
    g<<fixed<< setprecision(6) << sqrt(cmap(0,n-1));
}