Cod sursa(job #2072751)

Utilizator SchopenhauerIordache Stefan Schopenhauer Data 22 noiembrie 2017 10:31:43
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 4.82 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <list>
#include <vector>
#include <utility>
#include <cmath>
#include <cfloat>

using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

struct Point
{
    int x,y;
};

int CompareX(const void *A, const void *B)
{
    Point *a = (Point *)A;
    Point *b = (Point *)B;
    return (a->x - b->x);
}

int CompareY(const void *A, const void *B)
{
    Point *a = (Point *)A;
    Point *b = (Point *)B;
    return (a->y - b->y);
}

double Distance(Point A, Point B)
{
    return sqrt((A.x - B.x)*(A.x - B.x)*1.0 +
                (A.y - B.y)*(A.y - B.y)*1.0);
}

pair<double, pair<Point, Point> > DistanceFor3OrLessPoints(Point points[], int nrPoints)
{
    pair<double, pair<Point, Point> > result;
    result.first = DBL_MAX;
    double newDistance;

    for (int i = 0; i < nrPoints-1; i++)
        for (int j = i+1; j < nrPoints; j++)
            if ((newDistance = Distance(points[i],points[j])) < result.first)
            {
                result.first = newDistance;
                result.second.first = points[i];
                result.second.second = points[j];
            }
    return result;
}

pair<double, pair<Point, Point> > PickBestPair(pair<double, pair<Point, Point> > A, pair<double, pair<Point, Point> > B)
{
    return (A.first < B.first)? A : B;
}



pair<double, pair<Point, Point> > MinOnStrip(Point strip[], int sizeOfStrip, pair<double, pair<Point, Point> > smallestDistance)
{
    pair<double, pair<Point, Point> > result = smallestDistance;
    double newDistance;

    for (int i = 0; i < sizeOfStrip-1; i++)
        for (int j = i+1; j < sizeOfStrip && (strip[j].y - strip[i].y) < result.first; j++)
            if ((newDistance = Distance(strip[i], strip[j])) < result.first)
            {
                result.first = newDistance;
                result.second.first = strip[i];
                result.second.second = strip[j];
            }

    return result;
}

pair<double, pair<Point, Point> > FindClosestPairOfPoints(Point pointsX[], Point pointsY[], int nrPoints)
{
    pair<double, pair<Point, Point> > result;

    if (nrPoints <= 3)
        return DistanceFor3OrLessPoints(pointsX,nrPoints);
    else
    {

        int middlePointPosition = nrPoints/2;
        Point middlePoint = pointsX[middlePointPosition];

        Point leftSidePoints[middlePointPosition + 1];
        Point rightSidePoints[nrPoints - middlePointPosition - 1];
        int leftPosition = 0;
        int rightPosition = 0;

        for (int i = 0; i < nrPoints; i++)
        {
            if (pointsY[i].x <= middlePoint.x)
            {
                leftSidePoints[leftPosition++] = pointsY[i];
            }
            else
            {
                rightSidePoints[rightPosition++] = pointsY[i];
            }
        }

        pair<double, pair<Point, Point> > smallestDistanceLeft = FindClosestPairOfPoints(pointsX,
                                                                                         leftSidePoints,
                                                                                         middlePointPosition);
        pair<double, pair<Point, Point> > smallestDistanceRight = FindClosestPairOfPoints(pointsX + middlePointPosition,
                                                                                          rightSidePoints,
                                                                                          nrPoints - middlePointPosition);
        pair<double, pair<Point, Point> > smallestDistance = PickBestPair(smallestDistanceLeft,
                                                                                            smallestDistanceRight);

        Point strip[nrPoints];
        int nrPointsOnStrip = 0;
        for (int i = 0; i< nrPoints; i++)
        {
            if (abs(pointsY[i].x - middlePoint.x) < smallestDistance.first)
            {
                strip[nrPointsOnStrip] = pointsY[i];
                nrPointsOnStrip++;
            }
        }

        return PickBestPair(smallestDistance, MinOnStrip(strip, nrPointsOnStrip, smallestDistance));
    }
}

int main() {

    int nrPoints;
    Point point;

    f>>nrPoints;

    Point pointsX[nrPoints];
    Point pointsY[nrPoints];

    for (int i = 0; i < nrPoints; i++)
    {
        f>>point.x>>point.y;
        pointsX[i] = point;
        pointsY[i] = point;
    }

    qsort(pointsX, nrPoints, sizeof(Point), CompareX);
    qsort(pointsY, nrPoints, sizeof(Point), CompareY);

    pair<double, pair<Point, Point> > result = FindClosestPairOfPoints(pointsX, pointsY, nrPoints);

    //g<<"A("<<result.second.first.x<<", "<<result.second.first.y<<")\n";
    //g<<"B("<<result.second.second.x<<", "<<result.second.second.y<<")\n";
    //g<<"Distance between A and B: "<<result.first<<'\n';
    g<<result.first<<'\n';

    f.close();
    g.close();

    return 0;
}