Pagini recente » Cod sursa (job #1066756) | Cod sursa (job #1969582) | Cod sursa (job #1654395) | Cod sursa (job #700560) | Cod sursa (job #1537785)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
struct punct{ double x, y; };
auto by_x = [](const punct& a, const punct& b){
return a.x < b.x || (a.x == b.x && a.y < b.y); };
auto by_y = [](const punct& a, const punct& b){
return a.y < b.y || (a.y == b.y && a.x < b.x); };
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); }
double cmap(const vector<punct>& pts, int st, int dr, vector<punct>& pts_by_y){
if(dr-st+1 <= 3){
pts_by_y.resize(dr-st+1);
copy(begin(pts)+st, begin(pts)+dr+1, begin(pts_by_y));
sort(begin(pts_by_y), end(pts_by_y), by_y);
double rez = 2e9;
for(int i = st; i <= dr; ++i){
for(int j = i+1; j <= dr; ++j){
rez = min(rez, dist(pts[i], pts[j])); } }
return rez; }
const int mij = st + (dr-st+1)/2;
vector<punct> pts_by_y_st, pts_by_y_dr;
const double rez_st = cmap(pts, st, mij, pts_by_y_st), rez_dr = cmap(pts, mij+1, dr, pts_by_y_dr);
double rez = min(rez_st, rez_dr);
pts_by_y.resize(dr-st+1);
merge(begin(pts_by_y_st), end(pts_by_y_st), begin(pts_by_y_dr), end(pts_by_y_dr),
begin(pts_by_y), by_y);
vector<punct> pts_mijloc;
copy_if(begin(pts_by_y), end(pts_by_y), back_inserter(pts_mijloc),
[&pts, mij, rez](const punct& p){ return abs(p.x - pts[mij].x) <= rez; });
for(int i = 0; i < pts_mijloc.size(); ++i){
for(int j = i-1; j >= 0 && pts_mijloc[i].y - pts_mijloc[j].y <= rez; --j){
rez = min(rez, dist(pts_mijloc[i], pts_mijloc[j])); } }
return rez; }
int main(){
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
f >> n;
vector<punct> pts(n);
for(auto& p : pts){
f >> p.x >> p.y; }
sort(begin(pts), end(pts), by_x);
vector<punct> pts_by_y;
g << fixed << setprecision(6) << cmap(pts, 0, n-1, pts_by_y);
return 0; }