Cod sursa(job #2495850)

Utilizator FrincuFrinculeasa Alexandru Frincu Data 19 noiembrie 2019 21:35:10
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define inf 9007199254740992;

int k;

struct point
{
   double x,y;
}p1,p2;


double distanta(double x1,double y1,double x2,double y2)
{
    double r;
    r=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    return r;
}

struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};

double distpc(int l,int r,vector<pair<double,double>> v)
{

    int i,j,n;
    n=r-l+1;
    double d,dmin=inf;
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
        {
            //cout<<l<<" "<<i<<" "<<j<<"\n";
            d=distanta(v[l+i].first,v[l+i].second,v[l+j].first,v[l+j].second);
            if(d<dmin)
            {
                //cout<<"*"<<l<<" "<<i<<" "<<j<<"\n";
                dmin=d;
                p1.x=v[l+i].first;
                p1.y=v[l+i].second;
                p2.x=v[l+j].first;
                p2.y=v[l+j].second;

            }
        }
    return dmin;
}

double distanta_banda(int n,vector<pair<double,double>> vb)
{
    int i,j;
    double dmin=inf;
    sort(vb.begin(), vb.end(), sort_pred());
    for(i=0;i<n;i++)
        if(i+8>n)
        for(j=i+1;j<n;j++)
         {
            double d;
            d=distanta(vb[i].first,vb[i].second,vb[j].first,vb[j].second);
             if(d<dmin)
            {
                //cout<<"&"<<i<<" "<<j<<"\n";
                dmin=d;
                p1.x=vb[i].first;
                p1.y=vb[i].second;
                p2.x=vb[j].first;
                p2.y=vb[j].second;

            }
         }
         else
         {
           for(j=i+1;j<i+8;j++)
         {
            double d;
            d=distanta(vb[i].first,vb[i].second,vb[j].first,vb[j].second);
             if(d<dmin)
            {
                //cout<<"&"<<i<<" "<<j<<"\n";
                dmin=d;
                p1.x=vb[i].first;
                p1.y=vb[i].second;
                p2.x=vb[j].first;
                p2.y=vb[j].second;

            }
         }
         }
    return dmin;
}


double distmin(int l,int r,vector<pair<double,double>> v)
{
    double n,dn,d_banda,d_stanga,d_dreapta,dmin,n_vb=0;
    int mid;
    pair<double,double>midpc;
    n=r-l+1;
    if(n<=3)
    {
        dn=distpc(l,r,v);
        return dn;
    }
    else
    {
        mid=(l+r)/2;
        midpc=v[mid];
        d_stanga=distmin(l,mid,v);
        d_dreapta=distmin(mid+1,r,v);
        dmin=min(d_stanga,d_dreapta);
        vector<pair<double,double>> vb;
        for(int i=0; i<n; i++)
            if(abs(v[i].first-midpc.first)<=dmin)
            {
                vb.push_back(v[i]);
                n_vb++;
            }
        d_banda=distanta_banda(n_vb,vb);
    }
    return min(dmin,d_banda);
}



int main()
{


    int n,i;
    double x,y;
    vector<pair<double,double>>v;
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    f>>n;
    for(i=0; i<n; i++)
    {
        f>>x>>y;
        v.push_back(make_pair(x,y));
    }
    sort(v.begin(), v.end());
    for(i=0; i<n; i++)
    {
       // cout<<v[i].first<<" "<<v[i].second<<"\n";
    }

    g<<distmin(0,n-1,v);
    return 0;
}