Codeforces - 598C Nearest vectors

Codeforces - 598C Nearest Vectors 解题报告，高精度问题

从系统的角度来看，给定一个算法问题和输入，要使得计算机输出正确的结果，那么必须保证至少下面三个环节是正确无误的。

  • 算法设计 （思维上的构建）
  • 算法实施 （代码上的构建）
  • 算法运行 （计算机硬件上的构建）

这其中的任一环节出现了错误，都无法保证最终的正确结果。前两个环节主要取决于人的能力（理解问题，解决问题）与细心程度，而最后一个环节重点在于人对计算机的底层理解。换句话说，即使问题在我们的脑海中已被完美解决，但在算法运行时，计算机对该问题的重新表达可能会出现偏差。最常见的偏差就是计算机精度问题，毕竟是以离散来逼近连续，出现『精确的错误』是在所难免的。但当正确性和高精度只能二选一时，显然没有人会因为高精度而追求精确的错误。这篇文章就以Codeforces 598C这道题来探讨第三个环节算法运行中的精度问题。这道题目本身并不难，但在正式比赛中只有57个人AC，仅低于F题。说其不难，是因为算法设计以及算法实施环节太显而易见了，但这么低的AC率就是因为大多数人在这道题精度上出了问题。

问题描述

CF-598C-P.jpg

这道题的基本意思是说，给定n个二维向量，找出夹角（小于180度的那个夹角）最小的那两个向量出来。

初步思考

分析

读罢此题，感觉这也太简单不过了。既然要找出夹角最小的两个向量出来，那么只要计算出任意两两向量的夹角，然后找到其中最小的不就好了么。但仔细一想，其实没有必要对任意两两向量进行计算，因为给定一个向量，离它最近的向量无外乎是顺时针方向或者逆时针方向最近的。这也给了我们第一个优化算法的思路，

优化1：先对这n个二维向量按照从(1,0)向量的逆时针夹角进行排序，然后计算相邻向量的夹角

代码

相应的代码实现如下所示， 

 1: from math import *
 2: #stores counterclockwise angle between vector (1,0) and each vector in a
 3: a = []
 4: n = int(input())
 5: for _ in range(n):
 6:     x,y = map(int,input().split())
 7:     #calculate counterclockwise angle between (1,0) and this vector
 8:     t = acos(x/sqrt(x**2+y**2))
 9:     a.append([2*pi-t,t][y>=0])
10: #sorting a
11: b = sorted(a)
12: #calculate difference of angle between adjacent vectors
13: c = [b[i+1]-b[i] for i in range(n-1)]
14: c.append(b[-1]-b[0])
15: c = [[2*pi-foo,foo][foo<pi] for foo in c]
16: #find the nearest vectors
17: i_min = c.index(min(c))
18: if i_min!=n-1:
19:     i1 = a.index(b[i_min+1])
20:     i2 = a.index(b[i_min])
21: else:
22:     i1 = a.index(b[0])
23:     i2 = a.index(b[-1])
24: print(i1+1,i2+1)

然而正如文章头所说的，这段算法遇到了高精度问题。第119号测试数据如下，其中的第一和第二个向量极其接近，同时第三和第四个向量也非常接近，因此导致了麻烦。那么到底哪里出了问题？以及如何解决呢？

CF-598C-T119.jpg

精度问题

分析

浮点数在计算机中以二进制形式表达，因此其精度必然面临着二进制表达位数的限制。但如果你以为，无限的提高二进制表达位数，就可以获得某些浮点数的真实值的话，那就错了。这是因为某些十进制小数，用二进制表达的话，也会出现类似十进制小数中的无穷循环。举个例子十进制的0.1，其二进制表达为 0.0001100110011001100110011001100110011001100110011... 。因此无论增加多少二进制表达存储位数，都无法真正表达0.1的真实值。因此，计算机中往往保留的只是其近似值。再以 python 举个例子， 

>>> .1 + .1 + .1 == .3
False
>>> round(.1 + .1 + .1, 10) == round(.3, 10)
True

因此，尽管二进制小数的精度问题似乎没有很好的解决方案，但当我们遇到类似小数高精度问题时，一定要多加留心。类似的讨论，请参考浮点数算法：争议和限制。

那么面对这类高精度问题，我们可以有如下两种解决办法，

  • 提高程序中的变量精度要求，如单精度变为双精度（ float -> dobule -> long double ）
  • 另辟蹊径

对第一种方法而言 python 无法声明数据类型，其默认浮点类型等价于 c++ 中的 double 类型，因此必须借助于第三方的package来达到此目的，比如说，

这样一来，应该可以应付绝大多数问题。但如果这些已有的高精度数据类型还是不够高，那怎么办？本文，接下来就来提供另一种思路。

高精度等价表达

首先，我们再审一遍题，本题的目的是要找到夹角最小的两个向量。我们的解决办法是先按极角对向量排序，然后计算相邻向量的夹角或者夹角等价表达式，最后找出最小的。这只是问题到答案的一条路径，而该路径借助于度量相邻向量之间的夹角。但最终的答案只是要我们找出最接近的两个向量，而并不需要知道他们到底有多近，换句话说这道题不是基数优化，而是序数优化。那既然不去算相邻向量的夹角或等价表达式，那应该怎么办呢？值得注意的是，到目前为止，我们衡量任意两向量$a,b$的夹角$θab$都是用的如下表达式，

$$ \cos \theta_{ab} = \frac{a \cdot b}{\Vert a \Vert \Vert b \Vert} $$

那么如果向量$a,b$是我们最终的答案，那对任意其他向量$c,d$（假设其夹角为 \(\theta_{cd}\) ），会有什么样的结果呢？显然，那就是

$$\cos \theta_{ab} = \frac{a \cdot b}{\Vert a \Vert \Vert b \Vert} \ge \frac{c \cdot d}{\Vert c \Vert \Vert d \Vert} = \cos \theta_{cd}$$

既然是因为浮点数据中的小数带来的精度问题，那干脆我们就不要除法和求根了，简简单单的乘法和加法就不会损失精度了。

优化2：不考虑除法和求根，直接利用等价表达式来检验是否最优

换言之，我们通过，如下表达式，来判断$a,b$是否是最终的答案，

$$ (abs(a \cdot b) a \cdot b) (\Vert c \Vert \Vert d \Vert)^{2} \ge (abs(c \cdot d) c \cdot d) (\Vert a \Vert \Vert b \Vert)^{2} $$

代码

相应的代码如下所示 

 1: from math import *
 2: # stores counterclockwise angle between vector (1,0) and each vector in a
 3: a = []
 4: n = int(input())
 5: for i in range(n):
 6:     x,y = map(int,input().split())
 7:     # calculate counterclockwise angle between (1,0) and this vector
 8:     t = acos(x/sqrt(x**2+y**2))
 9:     a.append((i+1,[2*pi-t,t][y>=0],x,y))
10: cmp = lambda x:x[1]
11: a = sorted(a,key=cmp)
12: # construct pairs for adjacent vectors
13: b = []
14: for i in range(n):
15:     i1,i2 = a[i][0],a[(i+1)%n][0]
16:     x1,y1 = a[i][2:]
17:     x2,y2 = a[(i+1)%n][2:]
18:     inner_prod = x1*x2 + y1*y2
19:     inner_prod *= abs(inner_prod)
20:     norm_prod = ((x1**2+y1**2)*(x2**2+y2**2))
21:     b.append((i1,i2,inner_prod,norm_prod))
22: # find the nearest vectors
23: better = lambda p1,p2: p1[2]*p2[3]>p2[2]*p1[3]
24: ans = b[-1]
25: for i in range(n):
26:     if better(b[i],ans):
27: 	ans = b[i]
28: print(ans[0],ans[1])

反思

如果你耐心的看完了这篇文章，或许你会觉得这道题不值得一提，毕竟绝大多数情况下，不会出现这么变态的高精度测试数据。即使出现了，往往提高浮点数数据类型的精度也可以避免这个问题。但这篇文章，其实想说的还是 正本清源 ，认真理解题目的要求，而不去做要求以外的事情，走出思维的定式。下面简单总结了我的几点感悟，

  • 简单的方法可以处理大部分情况，复杂的方法只是为了迎合少数的情况
  • 具体到个人的要求，来选择简单方法还是复杂方法
  • 小心高精度浮点数陷阱
  • 遇到瓶颈了，试着对问题或者方法进行同构表达
  • 题目不要求准确值的话，尽量采取序数优化

本作品采用知识共享署名 2.5 中国大陆许可协议进行许可。欢迎转载，但请注明来自Mount Greenwicher的文章《Codeforces - 598C Nearest vectors》，并保持转载后文章内容的完整与无歧义。本人保留所有版权相关权利。

据说爱打赏的人运气都不会差

微信打赏

支付宝打赏

留言

新大陆被发现了次！
Feb 15 2016
▲