别就找i前面那一个
i附近10个左右多扫描一下(
by Killer_joke @ 2022-12-29 09:18:06
```c
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+50;
#define D double
struct spot{
D a[4];
}p[N];
D x,y,x_,y_,z,w,ans;
int n;
bool mmp(const spot &u,const spot &v){
return u.a[0]<v.a[0];
}
int main(){
scanf("%d",&n);
z=sin(1),w=cos(1); //旋转1弧度≈57°
for(int i=1;i<=n;i++){
scanf("%lf%lf",&x,&y);
x_=x*w-y*z;
y_=x*z+y*w; //计算旋转后的坐标
p[i].a[0]=x_;
p[i].a[1]=y_;
p[i].a[2]=x;
p[i].a[3]=y; //存下来
}
sort(p+1,p+n+1,mmp); //排序
for(int i=n+1;i<=n+10;i++)
p[i].a[0]=p[i].a[1]=-N-0.01; //边界处理
ans=2e9+0.01; //初始化答案
for(int i=1;i<=n;i++)
for(int j=1;j<=5;j++){ //枚举
x=p[i].a[2];y=p[i].a[3];
x_=p[i+j].a[2];y_=p[i+j].a[3];
z=sqrt((x-x_)*(x-x_)+(y-y_)*(y-y_)); //计算距离
if(ans>z)ans=z; //更新答案
}
printf("%.4lf\n",ans); //输出
}
/*
x'=xcosθ-ysinθ
y'=xsinθ+ycosθ
*/
```
nt
by pow_na @ 2022-12-29 09:19:52
rt
by pow_na @ 2022-12-29 09:20:18
@[__dest__ruct__or__](/user/592238)
by pow_na @ 2022-12-29 09:20:43
@[pow_na](/user/859089) 嗯,谢谢
by Eirin_Yagokoro @ 2022-12-29 10:13:58
@[Killer_joke](/user/915814) 好,我试试
by Eirin_Yagokoro @ 2022-12-29 10:14:32
@[Killer_joke](/user/915814) 谢谢,AC 了
by Eirin_Yagokoro @ 2022-12-29 10:54:56
你们可能都想复杂了
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX=1e4+7;
ll n;
double x[MAX],y[MAX];
double dist(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double ans=1e9+7;
int main()
{
cin>>n;
for(ll i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=n;j++)
{
if(i!=j)
{
ans=min(ans,dist(x[i],y[i],x[j],y[j]));
}
}
}
printf("%.4lf",ans);
return 0;
}
```
直接暴力不就行了?
by white_w @ 2023-02-09 14:29:53
6
by wujinyi @ 2023-05-09 21:32:29
实际上你以x轴为优先,y轴为第二排序,实际上可能会造成一些错误
例如4个点(1,8),(2,2),(3,9),(4,2)
当前点为(2,2),他的下一个为(3,9),但是实际上距离(2,2)最近的点应该是(4,2),
你可以另外建立一个序列,以y坐标为第一排序,x坐标为第二排序得到:
(2,2),(4,2),(1,8),(3,9),
这样(2,2)的距离最近就是(4,2)了
综合两个序列考虑,就可以得到真正的最小值
这个回复时间有点久远了,不过留给其他人看吧
by KouMoSir @ 2023-09-12 16:51:16