Cod sursa(job #2070896)

Utilizator PopaAdrianPopa Tiberiu Adrian PopaAdrian Data 20 noiembrie 2017 00:00:02
Problema Cele mai apropiate puncte din plan Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
vector < pair < int , int > > P;
struct customSort {
    bool operator()(const std::pair <int,int> &left, const std::pair <int,int> &right) {
        if(left.first!=right.first)
            return left.first < right.first;
        else
            return left.second < right.second;
    }
};
double CALCULATE_DISTANCE( pair < int, int> a, pair< int, int> b) {
    return (a.first-b.first) * (a.first-b.first)+ (a.second - b.second) * (a.second - b.second);
}
bool cmp(pair<int,int> a, pair<int,int>b)
{
    return a.second < b.second;
}
double FIND_CLOSEST_PAIR(int left, int right) {
    if((right-left)==1)
        return CALCULATE_DISTANCE(P[right],P[left]);
    if((right-left)==2){
        int minimum=CALCULATE_DISTANCE(P[left],P[left+1]);
        if(CALCULATE_DISTANCE(P[left],P[right])<minimum)
            minimum=CALCULATE_DISTANCE(P[left],P[right]);
        if(CALCULATE_DISTANCE(P[left+1],P[right])<minimum)
            minimum=CALCULATE_DISTANCE(P[left+1],P[right]);
        return minimum;
    }
    int median = (right+left)/2;    // DIVIDE
    int closest_value = min(FIND_CLOSEST_PAIR(left, median), FIND_CLOSEST_PAIR(median+1, right));   // CONQUER
    vector < pair < int , int > > Y;    // COMBINE
    for(int i=left;i<=right;i++)
        if(abs(P[i].first-P[median].first)<=(int)(ceil(sqrt(closest_value))))
            Y.push_back(std::make_pair(P[i].first,P[i].second));
    sort(Y.begin(),Y.end(),cmp);
    for(unsigned int i=0;i<Y.size();i++)
        for(unsigned j=i+1;j<=i+7&&j<Y.size();j++)
            closest_value = min(closest_value, (int)CALCULATE_DISTANCE(Y[i],Y[j]));
    return closest_value;
}
int main(){
    ifstream f("cmap.in");
    ofstream g("cmap.out");
    unsigned int n;
    f>>n;
    for(unsigned int i=0;i<n;i++){
        int x,y;
        f>>x>>y;
        P.push_back(std::make_pair(x,y));
    }
    std::sort( P.begin() , P.end(), customSort());
    g<<fixed<<setprecision(6)<<sqrt(FIND_CLOSEST_PAIR(0,n-1));
    f.close();
    g.close();
}