Cod sursa(job #1472481)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 17 august 2015 09:32:10
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>
#define MAX 100005
#define INF 4e18
#define x first
#define y second
#define ll long long
#define pll pair<ll, ll>
using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

int n, i, j;
vector<pll> ordX, ordY, v(MAX);

ll dist(pll a, pll b){
  return pow(a.x - b.x, 2) + pow(a.y - b.y, 2);
}

ll sol(int s, int d);

int main(){
  f >> n;
	ordX.resize(n), ordY.resize(n);
  for(i = 0; i < n; i++)
    f >> ordX[i].x >> ordX[i].y;
  sort(ordX.begin(), ordX.end());
	for(i = 0; i < n; i++)
		ordY[i] = make_pair(ordX[i].y, ordX[i].x);
	g << fixed << setprecision(6) << sqrt(sol(0, n));
  return 0;
}

ll sol(int s, int d){
	if(s >= d - 1)
		return INF;

 	if(d - s == 2){
		if(ordY[s] > ordY[s + 1])
			swap(ordY[s], ordY[s + 1]);
    return dist(ordX[s], ordX[s + 1]);
	}
  
	int mij = (s + d) / 2;
  ll mins = sol(s, mij), mind = sol(mij, d);
  ll min = mins < mind ? mins : mind;
  
	merge(ordY.begin() + s, ordY.begin() + mij, ordY.begin() + mij, ordY.begin() + d, v.begin());
	copy(v.begin(), v.begin() + (d - s), ordY.begin() + s);

	int size = 0;
	for(i = s; i < d; i++)
		if(abs(ordY[i].y - ordX[mij].x) < min)
			v[size++] = ordY[i];
	for(i = 0; i < size - 1; i++)
		for(j = i + 1; j < size && j < i + 8; j++){
			ll ds = dist(v[i], v[j]);
			min = min < ds ? min : ds;
		}
	return min;
}