Rt,我乱搞过了,代码很无脑,建议加强数据。
如果不能加强数据或许可以把此题降到绿?感觉正解也没有蓝的难度啊。
#include <bits/stdc++.h>
using namespace std;
pair<double, double> p, a[200005];
int tot, n;
double minn = 0x7fffffffffff;
inline double Dis(pair<double, double> a, pair<double, double> b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
bool cmp(pair<double, double> a, pair<double, double> b)
{
return a.first < b.first;
}
bool cmp2(pair<double, double> a, pair<double, double> b)
{
return a.second < b.second;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> p.first >> p.second;
a[++tot] = p;
}
sort(a + 1, a + tot + 1, cmp);
int i = 0;
while ((double)clock() / CLOCKS_PER_SEC <= 0.17 && ++i && i <= tot)
for (int j = i + 1; j <= tot; j++)
minn = min(minn, Dis(a[j], a[j - i]));
reverse(a + 1, a + tot + 1);
i = 0;
while ((double)clock() / CLOCKS_PER_SEC <= 0.36 && ++i && i <= tot)
for (int j = i + 1; j <= tot; j++)
minn = min(minn, Dis(a[j], a[j - i]));
sort(a + 1, a + tot + 1, cmp2);
i = 0;
while ((double)clock() / CLOCKS_PER_SEC <= 0.55 && ++i && i <= tot)
for (int j = i + 1; j <= tot; j++)
minn = min(minn, Dis(a[j], a[j - i]));
reverse(a + 1, a + tot + 1);
i = 0;
while ((double)clock() / CLOCKS_PER_SEC <= 0.76 && ++i && i <= tot)
for (int j = i + 1; j <= tot; j++)
minn = min(minn, Dis(a[j], a[j - i]));
random_shuffle(a + 1, a + tot + 1);
i = 0;
while ((double)clock() / CLOCKS_PER_SEC <= 0.97 && ++i && i <= tot)
for (int j = i + 1; j <= tot; j++)
minn = min(minn, Dis(a[j], a[j - i]));
printf("%.4f", sqrt(minn));
}