Cod sursa(job #2070764)

Utilizator MileaCarmenCarmen Milea MileaCarmen Data 19 noiembrie 2017 21:44:05
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 5.24 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>

using namespace std;

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

pair<pair<int,int>,pair<int,int>> minStripDist (vector<pair<int,int>> strip, float mini,pair<pair<int,int>,pair<int,int>> minPoint)
{
    for(int i=0;i<strip.size()-1;i++)
        for(int 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<int,int>,pair<int,int>> minDist(vector<pair<int,int>> vct_x, vector<pair<int,int>> vct_y, int 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
        float mini=dist(vct_x[0],vct_x[1]);
        pair<pair<int,int>,pair<int,int>> 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;
*/
    int mid=n/2; // gasim pozitia din mijlocul vectorului sortat dupa x
    pair<int,int> 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<int,int>> LeftYPoints;
    vector<pair<int,int>> RightYPoints;
    for(int 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<int,int>,pair<int,int>> leftMin=minDist(vct_x,LeftYPoints,LeftYPoints.size());
    vector<pair<int,int>> rightRemainder;
    for(int i=LeftYPoints.size();i<n;i++)
        rightRemainder.push_back(vct_x[i]);
    pair<pair<int,int>,pair<int,int>> rightMin=minDist(rightRemainder,RightYPoints,RightYPoints.size());

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

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

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

    for(int 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<int,int>,pair<int,int>> stripPoint=minStripDist(strip,miniDist,minPoint);

    if(stripPoint!=minPoint)
        return stripPoint;

    return minPoint;


}


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

    for(int i=0;i<n;i++)
    {
        pair<int,int> 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<int,int>,pair<int,int>> result=minDist(vct_x,vct_y,n);

    fout<<dist(result.first, result.second);

    return 0;
}