Pagini recente » Cod sursa (job #500043) | Cod sursa (job #1251753) | Cod sursa (job #341943) | Cod sursa (job #432972) | Cod sursa (job #1645946)
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct punct{
int x, y;
punct(){}
punct(const int a, const int b): x(a), y(b){} };
double dist(const punct& a, const punct& b){
const double dx = a.x - b.x, dy = a.y - b.y;
return sqrt(dx * dx + dy * dy); }
struct x_cmp{
bool operator()(const punct& a, const punct& b){
return a.x < b.x; } };
struct y_cmp{
bool operator()(const punct& a, const punct& b){
return a.y < b.y; } };
struct x_part{
double x;
x_part(const double x_): x(x_){}
bool operator()(const punct& a){
return a.x < x; } };
double closest_points(vector<punct>& pts){
// va lasa pts sortat dupa y
if(pts.size() < 4){
double rez = dist(pts[0], pts[1]);
for(int i = 0; i < pts.size(); ++i){
for(int j = i+1; j < pts.size(); ++j){
rez = min(rez, dist(pts[i], pts[j])); } }
sort(pts.begin(), pts.end(), y_cmp());
return rez; }
vector<punct>::iterator p_point = pts.begin() + pts.size()/2;
nth_element(pts.begin(), p_point, pts.end(), x_cmp());
const int x_mij = p_point -> x;
vector<punct> pts_left(pts.begin(), p_point), pts_right(p_point, pts.end());
const double rez_inter =
min(closest_points(pts_left), closest_points(pts_right));
merge(pts_left.begin(), pts_left.end(), pts_right.begin(), pts_right.end(),
pts.begin(), y_cmp());
vector<punct> strip;
for(int i = 0; i < pts.size(); ++i){
if(pts[i].x >= x_mij - rez_inter && pts[i].x <= x_mij + rez_inter){
strip.push_back(pts[i]); } }
double rez = rez_inter;
for(int i = 1, left = 0; i < strip.size(); ++i){
for(int j = i-1; j >= 0 && strip[i].y - strip[j].y <= rez_inter; --j){
rez = min(rez, dist(strip[i], strip[j])); } }
return rez; }
int main(){
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
f >> n;
vector<punct> pts(n);
for(int i = 0; i < n; ++i){
f >> pts[i].x >> pts[i].y; }
g << fixed << setprecision(7) << closest_points(pts);
return 0; }