# Closest Pair

unknown
c_cpp
2 years ago
1.5 kB
1
Indexable
Never
``` struct Point {
long long x;
long long y;
};
struct ClosestPair
{
public:
int N;
vector<int> tmpt;
vector<Point> point;
ClosestPair(int N){
this->N = N;
tmpt.resize(N + 1);
point.resize(N + 1);
}

bool cmpxy(const Point& a, const Point& b) {
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}

bool cmpy(const int& a, const int& b) {
return point[a].y < point[b].y;
}

long long dis2(int i, int j) {
return (point[i].x - point[j].x) * (point[i].x - point[j].x)
+ (point[i].y - point[j].y) * (point[i].y - point[j].y);
}

long long sqr(long long x) {
return x * x;
}

long long Closest_Pair(int left, int right) {
long long d = LLONG_MAX;
if (left == right)
return d;
if (left + 1 == right)
return dis2(left, right);
int mid = (left + right) >> 1;
long long d1 = Closest_Pair(left, mid);
long long d2 = Closest_Pair(mid + 1, right);
d = min(d1, d2);
int i, j, k = 0;
for (i = left; i <= right; i++) {
if (sqr(point[mid].x - point[i].x) <= d)
tmpt[k++] = i;
}
sort(begin(tmpt), begin(tmpt) + k, cmpy);
for (i = 0; i < k; i++) {
for (j = i + 1; j < k && sqr(point[tmpt[j]].y - point[tmpt[i]].y) < d;
j++) {
long long d3 = dis2(tmpt[i], tmpt[j]);
if (d > d3)
d = d3;
}
}
return d;
}
};```