Cod sursa(job #2070836)

Utilizator MileaCarmenCarmen Milea MileaCarmen Data 19 noiembrie 2017 22:46:52
Problema Cele mai apropiate puncte din plan Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 5.44 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>

using namespace std;

double dist(pair<long,long> pct1,pair<long,long> pct2)
{
    return sqrt(double((pct1.first-pct2.first)*(pct1.first-pct2.first)+(pct1.second-pct2.second)*(pct1.second-pct2.second)));
}

pair<pair<long,long>,pair<long,long>> minStripDist (vector<pair<long,long>> strip, double mini,pair<pair<long,long>,pair<long,long>> minPoint)
{
    for(long i=0;i<strip.size()-1;i++)
        for(long j=i+1;j<strip.size()&&(strip[j].second-strip[i].second<mini);j++)
        if(dist(strip[i],strip[j])<mini)
    {
        mini=dist(strip[i],strip[j]);
        minPoint=make_pair(strip[i],strip[j]);
    }
    return minPoint;
}

pair<pair<long,long>,pair<long,long>> minDist(vector<pair<long,long>> vct_x, vector<pair<long,long>> vct_y, long n)
{
    if(n==2)
        return make_pair(vct_x[0],vct_x[1]);                                  //cand n=2
    if(n==3)                                                                  //sau n=3
    {                                                                         //putem calcula cele mai apropiate puncte
        double mini=dist(vct_x[0],vct_x[1]);
        pair<pair<long,long>,pair<long,long>> result;
        result.first=vct_x[0];
        result.second=vct_x[1];
                                                                        //prin "brute force"
        if(mini>dist(vct_x[0],vct_x[2]))
        {
                mini=dist(vct_x[0],vct_x[2]);        //sunt "base case"-uri
                result.first=vct_x[0];
                result.second=vct_x[2];
        }
        if(mini>dist(vct_x[1],vct_x[2]))
        {
                mini=dist(vct_x[1],vct_x[2]);
                result.first=vct_x[1];
                result.second=vct_x[2];
        }

        return result;

    }
 /*   cout<<"vx"<<endl;
    for(int i=0;i<n;i++)
        cout<<vct_x[i].first<<" "<<vct_x[i].second<<"          ";
        cout<<endl;

     cout<<"vy"<<endl;
     for(int i=0;i<n;i++)
        cout<<vct_y[i].first<<" "<<vct_y[i].second<<"          ";
        cout<<endl;
*/
    long mid=n/2; // gasim pozitia din mijlocul vectorului sortat dupa x
    while(mid>0&&vct_x[mid].first==vct_x[mid-1].first) mid--;
    pair<long,long> midPoint=vct_x[mid];  //acesta imparte vectorul initial in 2 subvectori de lungimi aproximativ egale


 //   cout<<"mid  "<<mid<<"cu val   "<<vct_x[mid].first<<" "<<vct_x[mid].second<<endl;

    vector<pair<long,long>> LeftYPoints;
    vector<pair<long,long>> RightYPoints;
    for(long i=0;i<n;i++)
    {
        if(vct_y[i].second<midPoint.first) // daca e in stanga puntului din mijloc
        {
                LeftYPoints.push_back(vct_y[i]);

        }                                      //vct_y are x-ul pe second, vct_x are x-ul pe first
        else
        {
            RightYPoints.push_back(vct_y[i]);

        }
    }

 /*   cout<<"leftypoints"<<endl;
    for(int i=0;i<LeftYPoints.size();i++)
        cout<<LeftYPoints[i].first<<" "<<LeftYPoints[i].second<<"          ";
        cout<<endl;

    cout<<"rightypoints"<<endl;
    for(int i=0;i<RightYPoints.size();i++)
        cout<<RightYPoints[i].first<<" "<<RightYPoints[i].second<<"          ";
        cout<<endl; */

    pair<pair<long,long>,pair<long,long>> leftMin=minDist(vct_x,LeftYPoints,LeftYPoints.size());
    vector<pair<long,long>> rightRemainder;
    for(long i=LeftYPoints.size();i<n;i++)
        rightRemainder.push_back(vct_x[i]);
    pair<pair<long,long>,pair<long,long>> rightMin=minDist(rightRemainder,RightYPoints,RightYPoints.size());

    double distL=dist(leftMin.first,leftMin.second);
    double distR=dist(rightMin.first,rightMin.second);

    double miniDist;
    pair<pair<long,long>,pair<long,long>> minPoint;
    if(distL<distR)
    {
        miniDist=distL;
        minPoint=leftMin;
    }
    else
    {
        miniDist=distR;
        minPoint=rightMin;
    }

    vector<pair<long,long>> strip; // strip va retine doar puncte care se afla la distanta maxima miniDist de dreapta
                                        //verticala de ecuatie x=midPoint.x

    for(long i=0;i<n;i++)
    {
        if((vct_y[i].second>=midPoint.first)&&vct_y[i].second-midPoint.first<miniDist)
            strip.push_back(make_pair(vct_y[i].second,vct_y[i].first));
        else if((vct_y[i].second<midPoint.first)&&midPoint.first-vct_y[i].second<miniDist)
            strip.push_back(make_pair(vct_y[i].second,vct_y[i].first));

    }

    pair<pair<long,long>,pair<long,long>> stripPoint=minStripDist(strip,miniDist,minPoint);

    if(stripPoint!=minPoint)
        return stripPoint;

    return minPoint;


}


int main()
{
    long n;
    ifstream fin;
    fin.open("cmap.in");
    ofstream fout;
    fout.open("cmap.out");
    vector<pair<long,long>> vct_x,vct_y;
    fin>>n;

    for(long i=0;i<n;i++)
    {
        pair<long,long> pct;
        fin>>pct.first>>pct.second; //first=x, second=y
        vct_x.push_back(make_pair(pct.first,pct.second));
        vct_y.push_back(make_pair(pct.second,pct.first));

    }

    sort(vct_x.begin(),vct_x.end()); // sortez punctele dupa  x
    sort(vct_y.begin(),vct_y.end()); // sortez punctele dupa y

    pair<pair<long,long>,pair<long,long>> result=minDist(vct_x,vct_y,n);

    fout<<std::fixed << std::setprecision(7)<<dist(result.first, result.second);

    return 0;
}