这题数据还能加强吗
查看原帖
这题数据还能加强吗
223797
Remake_楼主2020/9/16 21:22

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));
}
2020/9/16 21:22
加载中...