Cod sursa(job #2969161)

Utilizator LuciBBadea Lucian LuciB Data 22 ianuarie 2023 17:16:14
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>
using namespace std;

struct point {
	int x, y;
	bool operator < (const point& other) const {
        return ((y < other.y) || (y == other.y && x < other.x));
	}
};

const int NMAX = 1e5;
const int INF = 1e9;
point v[NMAX];

double dist(const point& a, const point& b) {
  return sqrt((double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y));
}

bool cmp(point a, point b) {
    return ((a.x < b.x) || (a.x == b.x && a.y < b.y));
}
set<point> s;

int main() {
	int n;
	FILE *fin, *fout;
    fin = fopen("cmap.in", "r");
    fout = fopen("cmap.out", "w");
    fscanf(fin, "%d", &n);
    for(int i = 0; i < n; i++) {
		fscanf(fin, "%d%d", &v[i].x, &v[i].y);
    }
    sort(v, v + n, cmp);
    /*for(int i = 0; i < n; i++) {
		cout << v[i].x << ' ' << v[i].y << endl;
    }
    cout << endl;*/
    double ans = dist(v[0], v[1]);
    s.insert(v[0]);
    s.insert(v[1]);
    int i = 2;
    while(i < n) {
        int j = i;
        while(j < n && v[j].x == v[i].x) {
            auto it1 = s.lower_bound({-INF - 1, v[j].y - (int)ans - 1});
            ///auto it2 = s.lower_bound({0, v[j].y + (int)ans + 1});
            /*cout << s.size() << endl;
            cout << j << ": " << endl;
			if(it1 != s.end())
            	cout << (*it1).x << ' ' << (*it1).y << endl; //' ' << (*it2).x << ' ' << (*it2).y << endl;
            else {
				//cout << i << endl;
            }*/
            int val = v[j].y + (int)ans + 1;
            for(auto it = it1; it != s.end() && (*it).y < val; it++) {
				point aux = (*it);
				ans = min(ans, dist(v[j], aux));
            }
            val = v[j].x - (int)ans - 1;
            for(auto it = s.begin(); it != s.end();) {
				if((*it).x < val) {
					it = s.erase(it);
				} else {
					it++;
				}
            }
            s.insert(v[j]);
			j++;
        }
        i = j;
    }
    fprintf(fout, "%.6f", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}