1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
for (auto i : x) cout << i << ' ';\
cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 205, K = 111;
struct Pt {
double x, y, z;
int id;
Pt (double _x = 0, double _y = 0, double _z = 0) : x(_x), y(_y), z(-z) {}
double dis (const Pt &o) {
return sqrt((x - o.x) * (x - o.x) + (y - o.y) * (y - o.y) + (z - o.z) * (z - o.z));
}
bool operator < (const Pt &o) const {
return x < o.x;
}
};
struct cmp {
bool operator () (Pt a, Pt b) {
return a.y < b.y;
}
};
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector <Pt> a(n);
for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y >> a[i].z, a[i].id = i;
sort(all(a));
set <Pt, cmp> s;
double ans = 1e12;
int ansx = -1, ansy = -1;
for (int i = 0, j = 0; i < n; ++i) {
while (j < n && a[i].x - a[j].x > ans) s.erase(a[j++]);
for (auto it = s.lower_bound(Pt(a[i].x, a[i].y - ans, a[i].z)); it != s.end() && it->y <= a[i].y + ans; ++it) {
double res = a[i].dis(*it);
if (ans > res) {
ans = res;
ansx = a[i].id;
ansy = it->id;
}
}
s.insert(a[i]);
}
if (ansx > ansy) swap(ansx, ansy);
cout << "WARNING: galaxy" << ansx + 1 << " and galaxy" << ansy + 1 << " in " << fixed << setprecision(10) << ans << " Uu\n";
}
|