三点不共线
题目描述
平面上有两个不同的点 $A$ 和 $B$,你需要找到另一个点 $C$ ,使得这三个点构成的 $\angle ACB$ 恰好为 $\alpha$。
需要注意的是,在下图中,$\angle 1$ 和 $\angle 2$ 都可以被认为是 $\angle ACB$ ,你只需让其中一个角为 $\alpha$ 即可。
输入描述:
每个测试文件均包含多个测试点。第一行输入一个整数 $T$ ($1\le T\le 2 \cdot 10^5$) 代表测试数据组数,每组测试数据描述如下:
第一行输入五个整数 $x_1$, $y_1$, $x_2$, $y_2$ 和 $\alpha$ ($-1000 \le x_1$, $y_1$, $x_2$, $y_2 \le 1000$; $1 \le \alpha \le 180^{\circ}$) 表示给定两点的坐标与需要构造的角度,保证两点不重合。
输出描述:
对于每组数据,你都需要在一行上输出两个实数 $x$ 和 $y$ ($-10^9 \le x$, $y \le10^9$) 表示 $C$ 点的横、纵坐标,数字彼此间通过单个空格间隔。
当你的答案所构成的角 $\angle ACB$ 与 $\alpha$ 的误差不超过 $10^{-6}$ 时,均会被视为正确。换句话说,当你的答案满足 $\frac{|\angle ACB - \alpha|}{\max(1,\alpha)} \le 10^{-6}$ 时,均会被视为正确。
示例1
输入
4
2 1 -1 -1 90
4 -1 1 3 100
1 1 1 2 60
9 2 5 4 36
输出
-1 1
4.178199262355 2.258649446766
1.866025403784 1.5
3.922316462825 -3.155367074351
说明
第一、二个测试点如下图所示。
备注:
如果有多个可能的答案,你只需要输出其中一种。
解题思路
给出一种与官方题解不同的做法。
做直线 $AB$ 的中点 $M$,并假设所求的 $C$ 在 $AB$ 的中线 $MC$ 上,同时有 $\angle MCB = \alpha / 2$。由三角公式知道 $\tan(\alpha/2) = \frac{d/2}{l}$,其中 $d$ 是直线 $AB$ 的长度,因此直线 $MC$ 长度就是 $l = \frac{d/2}{\tan(\alpha/2)}$。
向量 $\overrightarrow{BA} = (x_B - x_A, y_B - y_A)$,则向量 $\overrightarrow{MC} = (y_A - y_B, x_B - x_A)$,因为 $\overrightarrow{BA}$ 与 $\overrightarrow{MC}$ 互相垂直,因此只需满足 $\overrightarrow{BA} \cdot \overrightarrow{MC} = \mathbf{0}$ 即可。$\overrightarrow{MC}$ 的单位向量就是 $\overrightarrow{e} = \frac{\overrightarrow{MC}}{|\overrightarrow{MC}|}$。
所以最后 $(x_C, y_C)=(x_M, y_M)+l \cdot \overrightarrow{e}$。
AC 代码如下,时间复杂度为 $O(1)$:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
int x1, y1, x2, y2, a;
scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &a);
double d = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
double l = d / 2 / tan(a / 2.0 / 180 * acos(-1));
double dx = (y1 - y2) / d, dy = (x2 - x1) / d; // MC的单位向量为(dx, dy)
double x3 = (x1 + x2) / 2.0, y3 = (y1 + y2) / 2.0;
x3 += dx * l, y3 += dy * l;
printf("%.8f %.8f\n", x3, y3);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
参考资料
牛客小白月赛88 出题人题解:https://ac.nowcoder.com/discuss/1260072
标签:三点,le,angle,overrightarrow,MC,共线,y1,alpha From: https://www.cnblogs.com/onlyblues/p/18062056