题解 P1257 【平面上的最接近点对】
应吟吟
·
·
题解
结合blog食用效果更加
分析
题目中不是说了吗
那我们也要根据出题人的意图去写嘛(大雾
我们看一下数据范围
2≤n≤10000
这个时候，本题的一个坑点就出来了:
> $x$和$y$的范围呢？
虽然我是随手$long\ long$的(这不是好习惯吗)，但是我还是试了一下不开$ long\ long $$(no\ zuo\ no\ die)$，然后。。。你会惊奇的发现
这是不开$ long\ long $的提交
这是开了$long\ long$的提交
你可以看到这是两份完全一样的程序，除了
```cpp
#define ll long long
#define ll int
```
这个不同。
~~(十年$OI$一场空，没开$long\ long$见祖宗)~~
***
# 切入正题
我们直接暴力枚举两个端点，并计算出它们之间的距离，用一个数$ ans $维护最小值
距离就简单的用勾股定理求就好了
代码+注释 如下：
```cpp
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll int
using namespace std;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
template < class T > inline void read(T &x)
{
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
x = f ? -x : x;
}
#undef getchar()
template < class T > inline void write(T x)
{
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
const ll FFF=10000+5;
const ll inf=0x7fffffff;
ll n;
ll ans=inf;//定义+设置初始值
struct node
{
ll x,y;
}dian[FFF];//点(拼音看得懂的吧)，x、y是这个点的横纵坐标
ll dis(ll x1,ll x2,ll y1,ll y2)//勾股定理(P.S. 其实这里可以不用直接开方，直接比较距离的平方，最后再开方)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int main()
{
if(fopen("hhh.in", "r"))
{
freopen("hhh.in", "r", stdin);
freopen("hhh.out", "w", stdout);
}
ios::sync_with_stdio(false);
read(n);
for(int i=1;i<=n;++i)
{
read(dian[i].x);
read(dian[i].y);
}
for(int i=1;i<=n;++i)
{
for(int j=i+1;j<=n;++j)
{
ans=min(dis(dian[i].x,dian[j].x,dian[i].y,dian[j].y),ans);//暴力枚举并维护
}
}
printf("%0.4lf",(double)sqrt(ans));
return 0;
}
```
~~(码风邪教，勿介)~~
~~总的来说，这道题毕竟是道，还是比较简单的~~