Cod sursa(job #2911645)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 30 iunie 2022 21:22:27
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#include <bits/stdc++.h>

using namespace std;

int const N = 1e6 + 1;

struct punct
{
    double x, y;
} p[N];

inline bool cmp(punct a, punct b);
inline bool cmp_x(punct a, punct b);
inline bool cmp_y(punct a, punct b);

double dist(punct a, punct b)
{
    double difx = fabs(a.x - b.x);
    double dify = fabs(a.y - b.y);
    return sqrt(difx * difx + dify * dify);
}

double aux = INT_MAX;

double divide(int l, int r)
{
    if(r - l <= 1)
        return INT_MAX;
    int mid = (l + r) / 2;
    double lx = divide(l, mid);
    double rx = divide(mid, r);
    aux = min(aux, min(lx, rx)); // fixez lungimea delta
    double x_sep = p[mid].x; // x-ul dreaptei d


    vector <punct> a;
    vector <punct> b;

    for(int i = l; i < mid; i++)
    {
        if(p[i].x >= x_sep - aux)
            a.push_back(p[i]);
    }
    for(int i = mid; i < r; i++)
    {
        if(p[i].x <= x_sep + aux)
            b.push_back(p[i]);
    }
    // slectam doar ce in deptunghiul delta x 2*delta

    sort(a.begin(), a.end(), cmp_y);
    sort(b.begin(), b.end(), cmp_y); // sortam dupa y

    int pointLeft, pointRight;
    pointLeft = 0;
    pointRight = 0;
    double ans = aux;
    for(auto pointCurrent: a)
    {
        while(pointRight < b.size() and b[pointRight].y <= pointCurrent.y + aux) // +delta
        {
            pointRight ++;
        }
        while(pointLeft < b.size() and b[pointLeft].y < pointCurrent.y - aux)   // -delta
        {
            pointLeft ++;
        }
        if(pointLeft == b.size())
            break;
        for(int i = pointLeft; i < pointRight; i ++)
        {
            ans =  min(ans, dist(pointCurrent, b[i]));
        }
    }
    return ans;

}


// v = p
int main()
{
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");

    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> p[i].x >> p[i].y;
    }

    sort(p + 1, p + n + 1, cmp);

    cout << fixed << setprecision(6) << divide(1, n) << "\n";

    return 0;
}

inline bool cmp(punct a, punct b)
{
    if(a.x == b.x)
        return (a.y < b.y);
    return (a.x < b.x);
}
inline bool cmp_x(punct a, punct b)
{
    return (a.x < b.x);
}
inline bool cmp_y(punct a, punct b)
{
    return (a.y < b.y);
}