Cod sursa(job #767475)

Utilizator mi5humihai draghici mi5hu Data 13 iulie 2012 17:07:22
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.33 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <fstream>

#define NMAX 100001
using namespace std;

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

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

void read_() {
    ifstream fin("cmap.in");
    fin >> N;
    for (int i = 0; i < N; i++) {
        fin >> P[i].x >> P[i].y;
    }  
    fin.close();
}

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(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));      
}

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

double calc_dist_max3(int p1, int p2) {
    double min = D(P[p1].x, P[p1].y, P[p1 + 1].x, P[p1 + 1].y);
    if (p2 - p1 > 1) {
        min = min_(min, D(P[p1].x, P[p1].y, P[p2].x, P[p2].y));
        min = min_(min, D(P[p1 + 1].x, P[p1 + 1].y, P[p2].x, P[p2].y));   
    }
    return min;    
}

double solve_mid(double d, int Tsize) {
      for (int i = 0; i < Tsize - 1; i++) {
          for (int j = i + 1; j < Tsize && j <= i + 7; j++) {
              d = min_(d, D(TMP[i].x, TMP[i].y, TMP[j].x, TMP[j].y)); 
          }
      }      
      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);    
        
        int Tsize = 0;
        for (int i = p1; i <= p2; i++) {
            if (abs(P[i].x - midP.x) < d) {
                TMP[Tsize++] = P[i];                  
            }
        }         
        d = solve_mid(d, Tsize); 
        return d;             
    } 
}

int main() {
    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;
}