Remake_ @ 2020-09-16 21:22:12
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));
}
by Lynkcat @ 2020-09-16 21:31:33
@Miracle_Creator 我排序后取左右10个点就过了草,确实数据水/fad
#include<bits/stdc++.h>
using namespace std;
int n;
double ans;
struct node
{
double x,y;
}a[400000];
bool CMp(node a,node b)
{
return a.x<b.x;
}
int main()
{
cin>>n;ans=999999999999999.9;
for (int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,CMp);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=min(n-i,10);j++)
ans=min(ans,sqrt((a[i+j].x-a[i].x)*(a[i+j].x-a[i].x)+(a[i+j].y-a[i].y)*(a[i+j].y-a[i].y)));
}
printf("%.4f",ans);
}
by Lynkcat @ 2020-09-16 21:35:59
@Miracle_Creator 但是感觉这个数据貌似真的很难造???
by big_news @ 2020-09-16 21:45:02
平面最近点对随机化乱搞不是出了名的神仙做法吗
by liuhengxi @ 2020-10-05 22:22:44
接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。
我用int
存 x,y 还过了
by MCAdam @ 2020-11-04 21:56:00
数据确实太水了
by Cry_For_theMoon @ 2021-01-14 22:55:35
@Miracle_Creator 但严谨的证明并不容易吧qwq