2015年武汉科技大学“蓝桥杯”校内选拔赛题解

题目地址:2015年武汉科技大学“蓝桥杯”校内选拔赛

1001 Wavio序列
最长上升子序列(LIS)模板题,正向一遍LIS,反向一遍LIS,求个最大值即可。复杂度O(nlogn)。

1002 大正整数的加法
其实题目讲的很明白了,做小学生加法即可,注意除了最高位其他都要控制4位。

1003 到底有多少个三角形
暂缺。

1004 封闭曲线
显然公式是个多项式,求个方程即可。
目测多项式不会超过3次,不妨设\(f(x) = ax^3 + bx^2 + cx + d\),然后求解以下方程组算出系数:\(\begin{cases}
f(1) = 2 \\
f(2) = 4 \\
f(3) = 8 \\
f(4) = 14 \\
\end{cases}\)

1005 黑色星期五
日期瞎搞下就行了,打个巨表二分一下即可,代码太丑就不放出来了。

1006 木棒切割
POJ原题,暑假集训浩浩讲过,14级没做出来的自己拿着键盘到南3-513跪着去。
代码:https://github.com/fcbruce/ACM-ICPC/blob/master/code/POJ/1011_Sticks.cc

1007 能否找到正确答案
搜索,暂缺。

1008 素因子
签到题,先预处理出每个数的素因子即可。

1009 药丸
典型的卡特兰数,要使用高精度。

1010 最大异或值
暂缺。

1011 最优序列
dp随便搞下,维护下即可。

1012 做加法求和
题意是假的,其实是个哈夫曼编码,然后用stl中的优先队列会T,我手写堆+优化过的,好像可以线性搞过。

浅谈计算几何学中向量的一些应用

The sacred geometry of chance.

—— Shape Of My Heart

计算几何学是一门非常有趣而神秘的学科,她既有数学中的严谨,又有算法艺术中的神秘。计算几何的应用广泛,在计算机图形学、计算机辅助设计(CAD)、分子建模、制造业等领域中均有重要应用。

计算几何学的出现,大大推进了工业的发展。而计算几何中计算的精髓在于向量。不仅是计算几何学,在数学、物理学中,向量的应用也推动了他们的发展。

本文将讨论二维平面中向量的一些简单应用。

向量的定义和表示

向量(Vector, 也称作矢量),由方向和长度两个因素组成。在二维平面中,向量和点的表示方法是一样的。例如,一个二维向量可以简单地表示为:

\(\vec{a}=(x, y)\)

向量的表示方法虽然和点一样,但是它们的意义是不同的。向量之间有一些运算,比如:向量+向量=向量,点+向量=点,向量-向量=点,点-点=向量,而点+点这个运算没有任何意义。

向量的线性运算

向量的线性运算包括向量的加法、减法和数乘三种运算,下面直接给出C++代码:

 

向量的点积

点积,又被称为内积、数量积。顾名思义两向量的点积结果是一个数量。设向量\(\vec{a}=(x_1, y_1)\)和向量\(\vec{b}=(x_2, y_2)\)在同一平面内,其数量积为:$$\vec{a}\vec{b}= x_1x_2 + y_1y_2$$
其C++代码实现为:

那么,点积有什么具体的应用呢?让我们考虑下如何判断两条直线是否垂直(给出过直线的两点)。一个比较简单的想法是求出两条直线的方程,然后判断系数是否成比例。这个方法显然有些复杂,计算量比较大,而且还要考虑直接与坐标轴平行的情况。

不妨假设这两条直线分别为AB和CD。这时候我们再考察一下向量\(\vec{AB}\)和向量\(\vec{CD}\),这两向量正是两线段的方向向量,如果这两向量的数量积为零,那么这两条直线垂直。这种方法的具体实现和计算量都非常小,只要计算向量的点积,而且精度误差也较小。

向量的叉积

叉积,又被称为外积、向量积。显然和点积的结果不同,叉积的结果是一个向量,其方向需要用右手定则来确定。

首先给出二维计算几何中向量叉积的计算方法:

设向量\(\vec{a}=(x_1, y_1)\)和向量\(\vec{b}=(x_2, y_2)\)在同一平面内,则:$$\vec{a}\times \vec{b}=x_1y_2 – x_2y_1 = |\vec{a}||\vec{b}| \sin x$$
其C++代码实现为:

 

那么向量叉积具体有什么应用呢?让我们首先思考这样一个问题,已知平面上一三角形的三点(ABC)座标,如何计算这个三角形的面积。

首先一个简单的思路是取其中两点连起来作为底边,然后求另一点到底边的距离(高),然后根据 \(面积=\frac{底\times高}{2}\) 来计算三角形的面积。这个方法似乎很简单,但求高似乎是一个比较麻烦的问题。

其次一个简单粗暴的思路是利用海伦公式,直接求解三角形面积。这个方法比上一个思路简单很多了,但是其中有一个开平方的操作,这样带来的精度误差就比较大了。

还有一个求三角形面积的公式是\(S = \frac{|a||b|\sin C}{2}\)。这个公式比海伦公式更加简洁了,唯一的麻烦在于\(\sin C\)。这时候我们不妨回过头来看一下向量叉积的定义式,显然,求三角形的面积便可以用以下公式进行求解:
$$S = \frac{|\vec{a} \times \vec{b}|}{2}$$
利用上述公式,我们只需要减法、乘法、除法操作便能求出三角形的面积,不仅简单粗暴,而且精度损失也是非常小的。

事实上,叉积求的便是对应平行四边形的有向面积。

有了三角形面积的求解方法,让我们想一想多边形的面积该如何求解。这里的多边形按逆时针顺序给出其各个顶点的座标。

显然我们无法直接求解任意多边形的面积,不妨用化归转移的思想,我们把这个多边形剖成若干个三角形,我们只要求出各个三角形的面积,把它们加起来即可。由于用向量求出的是有向面积,我们只要按逆时针顺序直接做向量的叉积,而且也可以处理凹多边形。

上文笔者一直在强调有向,那么有向这个概念是如何体现的呢?我们不妨考虑一下这个问题:已知平面上一线段AB,问P点和AB的位置关系。P在有向线段\(\vec{AB}\)的左边?右边?还是所在直线上?

事实上我们只要求一次有向面积即可:计算\(\vec{AP} \times \vec{AB}\),如果结果为正,则在左边;结果为负,则在右边;如果结果为零,那么P位于AB所在直线上。

为什么呢,因为这里的方向其实是角度的方向:规定逆时针角度为正,顺时针角度为负。

这种判定,在计算几何学中通常被称为“to-left-test”,顾名思义就是判断点是否位于有向线段的左侧。

让我们不妨把问题扩展一下,如何判断点与三角形的关系?点位于三角形内部还是外部(为了简单起见,我们不考虑点位于三条边所在直线上)。

假设三角形三顶点为ABC,我们只要对点P与有向线段\(\vec{AB}\), \(\vec{BC}\), \(\vec{CA}\)做三次to-left-test,如果三次to-left-test的结果相同,那么就说明点P位于\(\triangle ABC\)的内部。

巧合的是,三次to-left-test一共有8种结果,而平面上三条直线能将一个平面分隔成7个部分,那么消失的那种情况在哪里呢?如果在曲面上,结果又是如何呢?

参考资料:
[1].算法导论(原书第3版)/(美)科尔曼(Cormen, T.H.)等著;殷建平等译;—北京:机械工业出版社,2013.
[2].算法竞赛入门经典——训练指南/刘汝佳,陈锋编著.—北京: 清华大学出版社,2012.
[3].计算几何/邓俊辉主讲.—学堂在线MOOC平台,2015.