Cod sursa(job #2070076)

Utilizator StriddRobert Stridd Data 19 noiembrie 2017 11:01:16
Problema Cele mai apropiate puncte din plan Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 4.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;


struct Point{
    long long x;
    long long y;

    const Point& operator=(const Point& P)
    {
        x = P.x;
        y = P.y;
        return P;
    }
    int operator==(const Point& P)
    {
        return (x == P.x && y == P.y);
    }
};

long long returnDist(Point& P1, Point& P2)
{
    return  (long long) (P2.x - P1.x) * (long long) (P2.x - P1.x) +
            (long long) (P2.y - P1.y) * (long long) (P2.y - P1.y);
}

int compByX(const Point& P1,const Point& P2)
{
    return P1.x < P2.x;
}

int compByY(const Point& P1,const Point& P2)
{
    return P1.y < P2.y;
}

vector<Point> Points;
vector<Point> PointsOY;


long long divideClosPoints(long long left, long long right)
{
    if(right - left == 1)
    {
        if(Points[left].y > Points[right].y )
        {
            Point X = PointsOY[left];
            PointsOY[left] = PointsOY[right];
            PointsOY[right] = X;
        }
        return returnDist(Points[left], Points[right]);
    }

    if(right - left == 2)
        {
            Point X;
            if(PointsOY[left].y > PointsOY[left+1].y &&
               PointsOY[left].y > PointsOY[right].y &&
               PointsOY[left+1].y > PointsOY[right].y )
            {
                X = PointsOY[left];
                PointsOY[left] = PointsOY[right];
                PointsOY[right] = X;
            }
           if(PointsOY[left].y > PointsOY[left + 1].y &&
              PointsOY[left].y > PointsOY[right].y &&
              PointsOY[left + 1].y < PointsOY[right].y)
            {
                X = PointsOY[left];
                PointsOY[left] = PointsOY[left+1];
                PointsOY[left+1] = X;

                X = PointsOY[right];
                PointsOY[right] = PointsOY[left + 1];
                PointsOY[left+1] = X;
            }
            if(PointsOY[left].y < PointsOY[left+1].y &&
                PointsOY[left].y > PointsOY[right].y )
            {
                X = PointsOY[right];
                PointsOY[right] = PointsOY[left];
                PointsOY[left] = X;
                X = PointsOY[left+1];
                PointsOY[left+1] = PointsOY[right];
                PointsOY[right] = X;
            }
            if(PointsOY[left].y < PointsOY[left+1].y &&
                PointsOY[left].y < PointsOY[right].y &&
                PointsOY[left+1].y > PointsOY[right].y)
            {
                X = PointsOY[left + 1];
                PointsOY[left+1] = PointsOY[right];
                PointsOY[right] = X;
            }
            return min(returnDist(Points[left], Points[left+1]),
            min(returnDist(Points[left+1], Points[right]),
                returnDist(Points[left], Points[right])));
        }

    long long middle = (left + right) / 2;
    long long dLeft = divideClosPoints(left, middle);
    long long dRight = divideClosPoints(middle, right);

    long long d = min(dLeft, dRight);
    long i, j;

    vector<Point> verticalSec;
    vector<Point> sol;


    i = left;
    j = middle + 1;

    while(i <= middle && j <= right)
    {
        if(PointsOY[i].y < PointsOY[j].y)
        {
            sol.push_back(PointsOY[i]);
            i++;
        }
        else
        {
            sol.push_back(PointsOY[j]);
            j++;
        }
    }

    while(i <= middle)
    {
        sol.push_back(PointsOY[i]);
        i++;
    }

    while(j <= right)
    {
        sol.push_back(PointsOY[j]);
        j++;
    }

    j = 0;

    for(i = left; i <= right; i++)
    {
        PointsOY[i] = sol[j++];
    }
    int check = 0;

    for(i = left; i <= right; i++)
    {
        if( abs(PointsOY[i].x - Points[middle].x) <= d)
        {
                   verticalSec.push_back(PointsOY[i]);
        }
    }

    long long sizeV = verticalSec.size();

     for(i = 0; i < sizeV - 1; i++)
        for(j = i + 1; j <= i + 7 && j < sizeV ; j++)
        {
            d = min(d, returnDist(verticalSec[i],verticalSec[j]));
        }
    return d;
}

int main()
{
    ifstream fileRead("cmap.in");
    ofstream fileWrite("cmap.out");
    long long nrPoints, i;

    Point P;

    fileRead >> nrPoints;

    for(i = 0 ; i < nrPoints; i++)
    {
        fileRead >> P.x >> P.y;
        Points.push_back(P);
        PointsOY.push_back(P);
    }

    long long dist = returnDist(Points[0],Points[1]);

    sort(Points.begin(),Points.end(),compByX);
    fileWrite << fixed << setprecision(6) << sqrt(divideClosPoints(0,nrPoints - 1));

    fileRead.close();
    fileWrite.close();
}