Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int int64_t
- #pragma GCC optimize("O3")
- using namespace std;
- inline int sqr(int x) {
- return x * x;
- }
- inline int dist(pair<int, int> x, pair<int, int> y) {
- return sqrt(sqr(x.first - y.first) + sqr(x.second - y.second));
- }
- inline int bruteSolution(vector<pair<int, int>>& v) {
- int ans = LLONG_MAX;
- for (int i = 0; i < v.size(); i++) {
- for (int j = i + 1; j < v.size() && j - i < 4; j++) {
- ans = min(ans, dist(v[i], v[j]));
- }
- }
- return ans;
- }
- int calculateAnswer(vector<pair<int, int>>& v, int l, int r) {
- if (l == r) {
- return LLONG_MAX;
- }
- int m = (l + r) / 2;
- int middle_x = v[m].first;
- int answer = min(calculateAnswer(v, l, m), calculateAnswer(v, m + 1, r));
- for (int i = l, j = m + 1; i <= m && j <= r;) {
- if (v[i] <= v[j]) {
- i++;
- } else {
- swap(v[i], v[j++]);
- }
- }
- vector<pair<int, int>> check;
- for (int i = l; i <= r; i++) {
- if (abs(v[i].first - middle_x) <= answer) {
- check.push_back(v[i]);
- }
- }
- return min(answer, bruteSolution(check));
- }
- int32_t main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- vector<pair<int, int>> pts;
- int x, y;
- while (cin >> x >> y) {
- pts.emplace_back(x, y);
- }
- sort(pts.begin(), pts.end());
- cout << calculateAnswer(pts, 0, pts.size() - 1);
- }
Advertisement
Add Comment
Please, Sign In to add comment