Cod sursa(job #2488059)

Utilizator VersinMadalinaVERSIN IONELA MADALINA VersinMadalina Data 6 noiembrie 2019 08:49:48
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

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

struct Point{
    int x,y;
};

bool compareX(Point a, Point b){
    return a.x<b.x;
}
bool compareY(Point a, Point b){
    return a.y<b.y;
}

int distance(Point a, Point b){
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}

int minDistance(vector<Point> v, int st, int dr){
    if(dr-st == 1)
        return distance(v[st], v[dr]);
    if(dr-st == 2){
        return min({distance(v[st],v[dr-1]), distance(v[st], v[dr]), distance(v[st+1], v[dr]) });
    }

    int m = (st + dr)/2;
    int dist1,dist2,dist_min,d;
    dist1 = minDistance(v, st, m);
    dist2 = minDistance(v, m+1, dr);
    dist_min = min(dist1,dist2);
    d = (int)ceil(sqrt(dist_min));

    vector<Point> t;
    for(int i=m; i<dr; i++)
        if(v[i].x - v[m].x <=d)
            t.push_back(v[i]);
        else
            break;
    for(int i=m-1; i>=st; i--)
        if(v[m].x - v[i].x <=d)
            t.push_back(v[i]);
       else
           break;

    sort(t.begin(),t.end(),compareY);
    for(int i=0; i<t.size(); i++){
        for(int j=i+1; j<=i+7 && j<t.size(); j++){
            dist_min = min(dist_min, distance(t[i], t[j]));
        }
    }
    return dist_min;
}
int main() {

    int n;
    vector<Point> points;
    f>>n;

    for(int i=0; i<n; i++){
        Point p;
        f>>p.x>>p.y;
        points.push_back(p);
    }
    sort(points.begin(),points.end(),compareX);

    g <<fixed<<setprecision(6) <<sqrt(minDistance(points, 0, n-1));

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

    return 0;




}