Cod sursa(job #767304)

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

#define NMAX 100001
using namespace std;

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

Point P[NMAX];
int N;

Point make_point(int X, int Y) {
    Point pct;
    pct.x = X;
    pct.y = Y;
    return pct;      
}

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

int myComp(const void * a, const void * b) {
    int X1, X2;
    X1 = (*(Point*)a).x;
    X2 = (*(Point*)b).x;
    if (X1 != X2) {
       return (X1 - X2);        
    } else {
       int Y1, Y2;
        Y1 = (*(Point*)a).y;
        Y2 = (*(Point*)b).y;
       return (Y1 - Y2);       
    }
}

float D(Point a, Point b) {
    return (sqrt((float)pow((a.x - b.x), 2) + (float)pow((a.y - b.y), 2)));      
}

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

float min_(float d1, float d2) {
    return (d1 < d2 ? d1 : d2);      
}

float solve_mid(float d, vector<Point> vs, vector<Point> vd) {
      vector<Point>::iterator itS, itD;
      for (itS = vs.begin(); itS != vs.end(); itS++) {
          Point ps = *itS;
          for (itD = vd.begin(); itD != vd.end(); itD++) {
              Point pd = *itD;
              if ((pd.x - ps.x) >= d) {
                  break;          
              }
              if (abs(ps.y - pd.y) < d) {
                  d = min_(d, D(ps, pd));          
              }
          }
      }
      
      return d;      
}

float solve(int p1, int p2) {
    if (p2 - p1 <= 2) {
        return calc_dist_max3(p1, p2);
    }     
    else {
        int mid = (p1 + p2) / 2;
        float d = min_(solve(p1, mid), solve(mid + 1, p2));
        vector<Point> vs;
        vector<Point> vd;
        int val = P[mid].x;
        
        int i = mid;
        while ((val - P[i].x) < d) {
              vs.push_back(P[i]);
              i--;      
        }
        i = mid + 1;
        while ((P[i].x - val) < d) {
              vd.push_back(P[i]);
              i++;      
        }
        d = solve_mid(d, vs, vd);
        return d;             
    } 
}
 
void print_vec() {
    for (int i = 0; i < N; i++) {
        printf("(%d, %d); ",P[i].x, P[i].y); 
    }     
}

int main() {
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    
    read_();
    qsort(P, N, sizeof(Point), myComp); 
    float d = solve(0, N-1);
    printf("%f", d);
    //print_vec();
    
    return 0;
}