Cod sursa(job #1520102)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 8 noiembrie 2015 12:25:31
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.43 kb
#include <stdio.h>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

//const int m = 1e9+7;
const double e = 1e-6;

//long long lgPow(long long a, long long b);
//int binarySearch(int x, int n);
//void sieve(int n);
//inline int gcd(int a, int b);
bool isBigger(double a, double b);
double dist(int a, int b, int x, int y);


//const int N = 100;
//int st[N+5], dr[50], sp[50];
//bool ciur[N+5];
//int a[N+5];
//int d[N+5];
//int v[N+5];
//char m[N+5][N+5];
//map <int, int> m;
//bool a[26];
//char s[N+5];
//string s;

int main()
{
    int n,i,x,y,j;
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    scanf("%d",&n);
    vector < pair <int, int> > ab;
    //vector < pair <int, int> > ord;
    ab.push_back(make_pair(0,0));
    //ord.push_back(make_pair(0,0));
    for(i = 1;i <= n;i++){
        scanf("%d %d",&x,&y);
        ab.push_back(make_pair(x,y));
        //ord.push_back(make_pair(y,x));
    }
    sort(ab.begin(),ab.end());
    //sort(ord.begin(),ord.end());
    double d = dist(ab[1].first, ab[1].second, ab[2].first, ab[2].second);
    for(i = 3;i <= n;i++){
        for(j = i-1;j >= 1;j--){
            if(ab[i].first - ab[j].first > d){
                break;
            }
            double dd = dist(ab[i].first, ab[i].second, ab[j].first, ab[j].second);
            d = min(d,dd);
        }
    }
    printf("%.6f",d);
    return 0;
}

//long long lgPow(long long a, long long b){
//    long long sol = 1;
//    while(b){
//        if(b&1){
//            sol = sol*a;
//        }
//        a = a*a;
//        b >>= 1;
//    }
//    return sol;
//}

//int binarySearch(int x, int n){
//    int step,i;
//    for(step = 1;step <= n;step <<= 1);
//    for(i = 0;step;step >>= 1){
//        if(i + step <= n && v[i+step] <= x){
//            i += step;
//        }
//    }
//    return i;
//}

//void sieve(int n){
//    int i,j;
//    for(i = 4;i <= n;i += 2){
//        ciur[i] = 1;
//    }
//    for(i = 3;i <= n;i += 2){
//        if(!ciur[i]){
//            for(j = 3*i;j <= n;j += i+i){
//                ciur[j] = 1;
//            }
//        }
//    }
//}

//inline int gcd(int a, int b){
//    if(b == 0) return a;
//    return gcd(b,a%b);
//}

bool isBigger(double a, double b){
    return a > b;
}

double dist(int a, int b, int x, int y){
    return sqrt((a-x)*1LL*(a-x)+(b-y)*1LL*(b-y));
}