Cod sursa(job #3145284)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 14 august 2023 16:38:56
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define pb push_back

struct Point{ll x; ll y;};
bool comp_x(Point &A, Point &B){return A.x<B.x;}
bool comp_y(Point &A, Point &B){return A.y<B.y;}

ll get_distance(Point A, Point B){
    return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

ll bruteforce(vector<Point> points){
    ll minim = LLONG_MAX;
    for(int i=0;i<(int)points.size();i++) for(int j=i+1;j<(int)points.size();j++){
            minim=min(minim, get_distance(points[i],points[j]));
    }
    return minim;
}

ll find_closest(vector<Point> x_sorted, vector<Point> y_sorted, int st, int dr){
    if(dr-st+1<=3)
        return bruteforce(y_sorted);

    int mid=(st+dr)/2;
    vector<Point> left_points;
    vector<Point> right_points;
    for(int i=st;i<=mid;i++)
        left_points.push_back(x_sorted[i]);
    for(int i=mid+1;i<=dr;i++)
        right_points.push_back(x_sorted[i]);

    ll dist_left=find_closest(x_sorted, left_points, st, mid);
    ll dist_right=find_closest(x_sorted, right_points, mid+1, dr);
    ll dist=min(dist_left, dist_right);

    vector<Point> strip;
    for(int i=0;i<(int)y_sorted.size();i++){
        if((y_sorted[i].x-x_sorted[mid].x)*(y_sorted[i].x-x_sorted[mid].x)<=dist)
            strip.push_back(y_sorted[i]);
    }

    for(int i=0;i<(int)strip.size();i++){
        for(int j=i+1;j<(int)strip.size() && (strip[j].y-strip[i].y)*(strip[j].y-strip[i].y)<=dist;j++){
            dist=min(dist,get_distance(strip[i],strip[j]));
        }
    }

    return dist;
}

void solve(){
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);

    int N; cin>>N;
    vector<Point> x_sorted;
    vector<Point> y_sorted;
    for(int i=0;i<N;i++){
        ll x, y; cin>>x>>y;
        x_sorted.push_back({x,y});
        y_sorted.push_back({x,y});
    }
    sort(x_sorted.begin(), x_sorted.end(), comp_x);
    sort(y_sorted.begin(), y_sorted.end(), comp_y);

    cout<<fixed<<setprecision(10)<<sqrt(find_closest(x_sorted, y_sorted, 0, N-1));
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    solve();
    return 0;
}