题解：UVA11186 正多边形 Circum Triangle

_Weslie_ · 2024-07-19 14:49:55 · 题解

题意简述

给你一个圆的半径 r 和圆上的 n 个点，然后任意选择三个点，会组成一个三角形。要输出所有符合要求的三角形面积之和。

思路

注意到是在圆上，因此任选三个点一定能组成三角形。

因为 n\le 500，所以考虑暴力枚举。

首先需要将极坐标转化为平面直角坐标，设极坐标下圆半径为 r，给定的角为 \alpha，平面直角坐标下横坐标为 x，纵坐标为 y。则：

• x=r\cos\alpha
• y=r\sin\alpha

这个其实蛮好证明的：

根据三角函数的定义，可得 \cos\alpha=\dfrac{x}{r} 和 \sin\alpha=\dfrac{y}{r} 两个式子。

移项即可得到上面的式子。

现在的问题在于如何快速计算任意三角形面积。

我们可以采用下面的方法：

优点：只有乘法。

缺点：a 和 h 难求。

缺点：\sin C 难求。

优点：三边使用两点距离公式 dis=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} 即可求。

缺点：因为要多次根号，所以常数特大，在 n\le 500 时过不去。

4. 向量叉积法

向量积可以被定义为：

模长：|\bold{a}\times \bold{b}|=|\bold{a}|\times |\bold{b}| \sin \alpha（在这里 \alpha 表示两向量之间的夹角（共起点的前提下），它位于这两个矢量所定义的平面上，0\le \alpha\le \pi。）

方向：\bold{a} 与 \bold{b} 的向量积的方向与这两个向量所在平面垂直，且遵守右手定则。（一个简单的确定满足“右手定则”的结果向量的方向的方法是这样的：若坐标系是满足右手定则的，当右手的四指从 \bold{a} 以不超过180度的转角转向 \bold{b} 时，竖起的大拇指指向是 \bold{c} 的方向。）（以上文段摘自百度百科）

观察法 2 的公式，不难注意到上面叉积的模长就是三角形面积的两倍。

但是我们如何快速求出叉积的模长呢？

下面是向量叉积的行列式定义（三维空间）：

若 \bold{a}=(u_1,u_2,u_3) 且 \bold{b}=(v_1,v_2,v_3)，则

不难发现，因为这张图是二维空间，所以 u_3 和 v_3 都是 0。

三个向量 \bold{i},\bold{j},\bold{k} 都是单位向量。

把它用行列式展开，得：

显然 u_3 和 v_3 是 0，所以前两项就不用管了。