Cod sursa(job #2493831)

Utilizator WoodsOfYpresAdora Vivos WoodsOfYpres Data 16 noiembrie 2019 23:31:10
Problema Cele mai apropiate puncte din plan Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;

double dist(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
bool cmp(pair<double,double> p1, pair<double,double> p2)
{
    if(p1.second-p2.second<0)
        return 1;
    else
        return 0;
}
double divide_et_impera(vector<pair<double,double> > points)
{
    double dist_min;
    if(points.size()==3)
    {
        double d12,d13,d23,maximum;
        d12=dist(points[0].first,points[0].second,points[1].first,points[1].second);
        d13=dist(points[0].first,points[0].second,points[2].first,points[2].second);
        d23=dist(points[1].first,points[1].second,points[2].first,points[2].second);
        maximum=d12;
        if(d13>maximum)
            maximum=d13;
        if(d23>maximum)
            maximum=d23;
        return maximum;
    }
    if(points.size()==2)
    {
        return dist(points[0].first,points[0].second,points[1].first,points[1].second);
    }
    //vector<pair<double,double> > pointsx(points);
    //sort(pointsx.begin(),pointsx.end());
    vector<pair<double,double> >::iterator it;
    it=points.begin();
    it+=points.size()/2;
    cout<<"size:"<<points.size()<<"\n";
    vector<pair<double,double> > left(points.begin(),it), right(it,points.end());
    cout<<"left size:"<<left.size()<<"\n";
    cout<<"right size:"<<right.size()<<"\n";
    double line=((*it).first+(*(it+1)).first)/2;
    double dist_min_r,dist_min_l;
    dist_min_l=divide_et_impera(left);
    dist_min_r=divide_et_impera(right);
    if(dist_min_l<dist_min_r)
        dist_min=dist_min_l;
    else
        dist_min=dist_min_r;
    vector<pair<double,double> > pointsy;
    for(int i=0;i<points.size();i++)
    {
        if(abs(points[i].first-line)<=dist_min)
            pointsy.push_back(points[i]);
    }
    sort(pointsy.begin(),pointsy.end(),cmp);
    int i,j;
    for(i=0;i<pointsy.size()-1;i++)
    {
        for(j=i+1;j<pointsy.size() && j<=i+8;j++)
        {
            double dist_aux=dist(pointsy[i].first,pointsy[i].second,pointsy[j].first,pointsy[j].second);
            if(dist_min>dist_aux)
                dist_min=dist_aux;
        }
    }
    return dist_min;
}
int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    int N,i,x,y;
    vector<pair<double,double> > points;
    in>>N;
    for(i=0;i<N;i++)
    {
        in>>x>>y;
        points.push_back(make_pair(x,y));
    }
    sort(points.begin(),points.end());
    out<<fixed<<setprecision(6)<<divide_et_impera(points);
    return 0;
}