目前的最好成绩是 $144$ 分。
代码如下:
```cpp
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define x first
#define y second
#define gc getchar
#define pc putchar
#define rep(i, a, b) for (register int i = (a); i <= (b); i ++ )
using namespace std;
void read() { return; }
template <typename T, typename ...T2>
void read(T &s, T2 &...oth) {
s = 0; char ch = gc(); bool f = 0;
for (; ch < '0' or ch > '9'; ch = gc()) if (ch == '-') f = 1;
for (; ch >= '0' and ch <= '9'; ch = gc()) s = (s << 1) + (s << 3) + (ch ^ 48);
s = f ? -s : s; read(oth...); return;
}
void write(char ch) { return; }
template <typename T, typename ...T2>
void write(char ch, T s, T2 ...oth) {
if (!s) { pc('0'); pc(ch); write(ch, oth...); return; }
int stk[100], top = 0;
if (s < 0) pc('-'), s = ~s + 1;
while (s) stk[ ++ top] = s % 10, s /= 10;
do pc(stk[top -- ] + (1 << 4) + (1 << 5)); while (top);
pc(ch); write(ch, oth...); return;
}
using ULL = unsigned long long;
using PII = pair<int, int>;
unordered_map<ULL, vector<int>> bin;
const int N = 400010;
const ULL B = 1331331ull;
const ULL P = 394730487ull;
const int dx[] = {0, 1, 1, 0, -1, -1, -1, 0, 1};
const int dy[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
PII p[N]; long long ans; int n;
ULL hs(int x, int y) {
return 1ull * x * P + 1ull * y;
}
void ins(double d, int x, int y, int i) {
bin[hs((int)x / d, (int)y / d)].push_back(i);
}
void build(double d, int r) {
bin.clear(); rep(i, 1, r)
ins(d, p[i].x, p[i].y, i);
}
double dis(PII a, PII b) {
double dx = a.x - b.x, dy = a.y - b.y;
return (double)sqrt(dx * dx + dy * dy);
}
long long dist(PII a, PII b) {
long long dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}
int main() {
read(n);
rep(i, 1, n) read(p[i].x, p[i].y);
sort(p + 1, p + n + 1); double d = 5 * dis(p[1], p[2]);
ans = dist(p[1], p[2]); build(d, 2);
rep(i, 3, n) {
int x = (int)p[i].x / d, y = (int)p[i].y / d, flg = 0;
rep(j, 0, 8) if (bin[hs(x + dx[j], y + dy[j])].size())
for (auto k : bin[hs(x + dx[j], y + dy[j])]) {
if (i != k and dist(p[i], p[k]) < ans) {
d = 5 * dis(p[i], p[k]), flg = 1;
ans = dist(p[i], p[k]);
}
}
if (flg) build(d, i);
else ins(d, p[i].x, p[i].y, i);
}
printf("%lld\n", ans);
}
```
by Link_Cut_Y @ 2024-02-27 14:52:49
试试fread和fwrite?
by Lin_JunHao @ 2024-02-28 18:58:47