PrevNext
Resources
IUSACO
6 - 完全搜索

本模块以此为基础


在许多问题中（尤其是铜组问题），检查解空间中的所有可能情况就足够了，无论是所有 元素、所有元素对、所有子集还是所有排列。顾名思义，这称为完全搜索（或 暴力搜索），因为它会完整地搜索整个解空间。

Maximum Distance
CF - Easy

Focus Problem – try your best to solve this problem before continuing!

解答——Maximum Distance

我们可以遍历每一对点，并利用欧几里得距离公式的平方求出它们之间距离的平方：

distance[(x1,y1),(x2,y2)]2=(x2−x1)2+(y2−y1)2.\text{distance}[(x_1,y_1),(x_2,y_2)]^2 = (x_2-x_1)^2 + (y_2-y_1)^2.

用 max_squared 维护当前最大的距离平方。

Warning!

请务必使用 PyPy 提交，因为该解法使用普通 Python 会超时。

n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))


max_squared = 0  # stores the current maximum
for i in range(n):  # for each first point
	for j in range(i + 1, n):  # and each second point
		dx = x[i] - x[j]
		dy = y[i] - y[j]
		square = dx * dx + dy * dy

有几点需要注意：

  • 由于我们要遍历所有点对，因此让 jj 循环从 j=i+1j=i+1 开始，使点 ii 和点 jj 永远不会是同一个点；这样也能保证每对点只被统计一次。在本题中，重复统计点对， 或允许 ii 与 jj 为同一点都不会影响结果。但在其他需要计数而非求最大值的 问题中，必须小心避免重复计数。
  • 其次，题目要求任意两点间最大欧几里得距离的平方。有些同学可能会想用整数变量 维护最大距离，最后输出时再将其平方。然而，虽然两个整数坐标点之间距离的平方 一定是整数，距离本身却不一定是整数。把非整数值存入整数变量会截去小数部分。

下面的解法正确地用浮点变量存储最大距离。

import math


n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))


max_dist = 0
for i in range(n):
	for j in range(i + 1, n):
		dx = x[i] - x[j]
		dy = y[i] - y[j]
		square = dx * dx + dy * dy
		max_dist = max(max_dist, math.sqrt(square))


print(int(max_dist**2))

但它仍无法通过下面的测试用例（程序输出 12，而正确答案是 13）：

2
0 3
2 0

四舍五入即可解决（round(MaxDistance ** 2)），但重点是：只要可以，就应坚持 使用整数。

题目

StatusSourceProblem NameDifficultyTags
Bronze
Milk Pails
Easy
Show TagsComplete Search
Bronze
Diamond Collector
Easy
Show TagsComplete Search
Bronze
Daisy Chains
Easy
Show TagsComplete Search
Bronze
Counting Liars
Medium
Show TagsComplete Search, Sorting
Bronze
Cow Gymnastics
Medium
Show TagsComplete Search
Bronze
Bovine Genomics
Medium
Show TagsComplete Search
Bronze
Triangles
Medium
Show TagsComplete Search
Bronze
Lifeguards
Medium
Show TagsComplete Search
Bronze
Why Did the Cow Cross the Road II
Medium
Show TagsComplete Search
Bronze
Guess the Animal
Hard
Show TagsComplete Search
Silver
Bovine Genomics
Hard
Show TagsComplete Search
Bronze
Load Balancing
Hard
Show TagsComplete Search
Bronze
Sleeping in Class
Hard
Show TagsComplete Search
Bronze
Cow Checkups
Hard
Show TagsComplete Search
Bronze
Contaminated Milk
Very Hard
Show TagsComplete Search
Bronze
Cowntact Tracing
Very Hard
Show TagsComplete Search
Bronze
Bull in a China Shop
Very Hard
Show TagsComplete Search
Silver
Load Balancing
Very Hard
Show TagsComplete Search
Bronze
Moo Language
Very Hard
Show TagsComplete Search

Module Progress:

PrevNext