Cod sursa(job #767468)

Utilizator mi5humihai draghici mi5hu Data 13 iulie 2012 16:52:18
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.75 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <limits>
#include <math.h>
#include <algorithm>

#define NMAX 100001
using namespace std;

typedef struct Point {
    int x;
    int y;        
} Point;

Point P[NMAX];
Point TMP[NMAX];
int N;

void read_() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d%d", &(P[i].x), &(P[i].y));
    }  
}

bool myComp_x(Point a, Point b) {
    if (a.x < b.x) {
       return true;
    }
    return false; 
}

bool myComp_y(Point a, Point b) {
    if (a.y < b.y) {
       return true;
    }
    return false;     
}

double D(Point a, Point b) {
    double x1, x2, y1, y2;
    x1 = (double)a.x;
    x2 = (double)b.x;
    y1 = (double)a.y;
    y2 = (double)b.y; 
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));      
}

double calc_dist_max3(int p1, int p2) {
    double min = (double)numeric_limits<double>::max();
    for (int i = p1; i < p2; i++) {
        for (int j = i + 1; j <= p2; j++) {
            double d = D(P[i], P[j]);
            if (d < min) {
               min = d;           
            }
        }
    }  
    return min;    
}

double min_(double a, double b) {
  return (a<b)? a : b;
}

void print_vec() {
    for (int i = 0; i < N; i++) {
        printf("(%d, %d); ",P[i].x, P[i].y); 
    }     
    printf("\n");
}
void print_v(vector<Point> vc) {
    for (int i = 0; i < vc.size(); i++) {
        printf("(%d, %d); ", vc[i].x, vc[i].y);
    }
    printf("\n");
}

double solve_mid(double d, vector<Point> vct) {
      for (int i = 0; i < vct.size() - 1; i++) {
          for (int j = i + 1; j < vct.size()&& j <= i + 7; j++) {
              d = min_(d, D(vct[i], vct[j])); 
          }
      }      
      return d;      
}

double solve(int p1, int p2) {
    if (p2 - p1 <= 2) {        
        sort(P + p1, P + p2 + 1, myComp_y);
        return calc_dist_max3(p1, p2);
    }     
    else {
        int mid = (p1 + p2) / 2;
        Point midP = P[mid];
        double d = min_(solve(p1, mid), solve(mid + 1, p2));
        
        merge(P + p1 , P + mid + 1 , P + mid + 1, P + p2 + 1, TMP, myComp_y);        
        copy(TMP, TMP + p2 - p1 + 1, P + p1);    
        
        vector<Point> v;
        for (int i = p2; i >= p1; i--) {
            if (abs(P[i].x - midP.x) < d) {
                v.push_back(P[i]);                  
            }
        }         
        d = solve_mid(d, v); 
        return d;             
    } 
}

int main() {
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    
    read_();
    sort(P, P + N, myComp_x); 
    //print_vec();
    double d = solve(0, N-1);
    printf("%.6lf", d);
    
    return 0;
}