Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(x) (x).begin(),(x).end()
- using namespace std;
- using ll = long long;
- struct pt {
- int x, y, i;
- bool operator < (const pt& o) {
- if (x != o.x) return x < o.x;
- return y < o.y;
- }
- };
- ll answer = 1e18;
- int ind1 = -1, ind2 = -1;
- const int MSIZE = 50505;
- pt buff[MSIZE];
- ll Dist(const pt& a, const pt& b) {
- return (a.x - b.x) * 1ll * (a.x - b.x) + (a.y - b.y) * 1ll * (a.y - b.y);
- }
- void DC(int tl, int tr, vector<pt>& arr) {
- if (tl + 1 < tr) {
- int tm = (tl + tr) / 2;
- DC(tl, tm, arr);
- DC(tm, tr, arr);
- int itr = 0;
- int xmid = arr[tm].x;
- for (int i = tl; i < tr; i++) {
- if ((xmid - arr[i].x) * 1ll * (xmid - arr[i].x) <= answer) {
- buff[itr++] = arr[i];
- }
- }
- sort(buff, buff + itr, [&] (const pt& a, const pt& b) {
- return a.y < b.y;
- });
- for (int i = 0; i < itr; i++) {
- for (int j = 1; j <= 8 && i + j < itr; j++) {
- if (answer > Dist(buff[i], buff[i + j])) {
- answer = Dist(buff[i], buff[i + j]);
- ind1 = buff[i].i;
- ind2 = buff[i + j].i;
- }
- }
- }
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n;
- cin >> n;
- vector<pt> arr(n);
- for (int i = 0; i < n; i++) {
- int x, y;
- cin >> x >> y;
- arr[i] = pt{x, y, i};
- }
- sort(all(arr));
- DC(0, n, arr);
- if (ind1 > ind2) swap(ind1, ind2);
- cout << ind1 << ' ' << ind2 << ' ';
- cout << fixed << setprecision(6) << sqrtl((long double) (answer)) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement