Cod sursa(job #1016723)

Utilizator jul123Iulia Duta jul123 Data 26 octombrie 2013 17:36:35
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
#include<iostream>
#include<fstream>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<iomanip>
using namespace std;
long long x[10000], y[10000];
long long pivot(int left, int right)
{
    long long  p1,p2,p3,p,mini,maxi;
    p1=x[left + rand() % (right-left+1)];
    p2=x[left + rand() % (right-left+1)];
    p3=x[left + rand() % (right-left+1)];
    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(int a, int b)
{
    return ((x[b]-x[a])*(x[b]-x[a])+(y[b]-y[a])*(y[b]-y[a]));
}
void quicksort(int left, int right)
{
    int i=left, j=right, tmp;
    long long piv;
    piv=pivot(left,right);
    while(i<=j)
    {
        while(x[i]<piv)
            i++;
        while(x[j]>piv)
            j--;
        if(i<=j)
        {
            tmp=x[i];
            x[i]=x[j];
            x[j]=tmp;
            tmp=y[i];
            y[i]=y[j];
            y[j]=tmp;
            if(x[i]==x[j])
            if(y[i]>y[j]){
                tmp=y[i];
                y[i]=y[j];
                y[j]=tmp;
            }

            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 1000000000;
    if(right-left==1)
        return dist(left, right);
    else if(right-left==2)
    {
        a=left;
        b=left+1;
        c=left+2;
        nr=min(dist(a,b),dist(a,c));
        nr=min(nr, dist(b,c));
    }
    else{
        mij=(left+right)/2;
        nr1=cmap(left, mij);
        nr2=cmap(mij, right);
        nr=min(nr1,nr2);
        a1=x[mij];
        i=mij-1;
        j=mij+1;
        while(a1-x[i]<=nr)
            i--;
        while(x[j]-a1<=nr)
            j++;
        i++;
        j--;
        for(t=i;t<=j-7;t++){
            for(k=1;k<=7;k++)
            {
            d=dist(t,t+k);
            if(d<nr && t<=mij && t+k>=mij)
                nr=d;}
        }
}
    }
return nr;
}
int main()
{
    int n, i;
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    f>>n;
    for(i=0;i<n;i++)
        f>>x[i]>>y[i];
    quicksort(0,n-1);
    g<<fixed<< setprecision(6) << sqrt(cmap(0,n-1));
}