题解 P1257 【平面上的最接近点对】

发表于 | 阅读次数：
本文字数： 1.9k | 阅读时长 ≈ 2 分钟

分析

题目中不是说了吗

那我们也要根据出题人的意图去写嘛(大雾

我们看一下数据范围

$ 2≤n≤10000 $

$emmm$，$O(n^2)$的好像可以$*$掉此题

这个时候，本题的一个坑点就出来了:

$x$和$y$的范围呢？

虽然我是随手$long\ long$的(这不是好习惯吗)，但是我还是试了一下不开$ long\ long $$(no\ zuo\ no\ die)$，然后。。。你会惊奇的发现

这是不开$ long\ long $的提交

这是开了$long\ long$的提交

你可以看到这是两份完全一样的程序，除了

1
2
#define ll long long
#define ll int

这个不同。

(十年$OI$一场空，没开$long\ long$见祖宗)

切入正题

我们直接暴力枚举两个端点，并计算出它们之间的距离，用一个数$ ans $维护最小值

距离就简单的用勾股定理求就好了

代码+注释 如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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;
}

(码风邪教，勿介)

总的来说，这道题毕竟是道，还是比较简单的