首页 > 试题广场 >

【模板】点线最近距离

[编程题]【模板】点线最近距离
  • 热度指数:54 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 1024M,其他语言2048M
  • 算法知识视频讲解
\hspace{15pt}在二维平面上有两个不同的点 A(x_A,y_A)B(x_B,y_B) 构成直线/线段 AB ,你需要构建一个数据结构,使得其能支持:
\hspace{22.5pt}_\texttt{1.}\点-直线最近点:输出点 C(x_c,y_c) 到直线 AB 的最近点;
\hspace{22.5pt}_\texttt{2.}\点-直线最近距离:输出点 C 到直线 AB 的最近距离;
\hspace{22.5pt}_\texttt{3.}\点-线段最近点:输出点 C 到线段 AB 的最近点;
\hspace{22.5pt}_\texttt{4.}\点-线段最近距离:输出点 C 到线段 AB 的最近距离。

输入描述:
\hspace{15pt}第一行输入一个整数 q \left( 1 \leqq q \leqq 5 \times 10^5 \right) 代表操作次数。

\hspace{15pt}此后 q 行,每行输入一个整数 op \left( 1 \leqq op \leqq 4 \right) 对应题干操作编号。随后在同一行输入六个整数 x_A,y_A,x_B,y_B,x_C,y_C \left( -10^6 \leqq x_A,y_A,x_B,y_B,x_C,y_C \leqq 10^6 \right) 代表直线上两点(或线段的两个端点)和待查询的点。保证点 A 和点 B 不同。


输出描述:
\hspace{15pt}对于每一次 op=1,3 的询问,在一行上输出两个实数代表最近点的横纵坐标。
\hspace{15pt}对于每一次 op=2,4 的询问,在一行上输出一个实数代表最近距离。

\hspace{15pt}如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
\hspace{15pt}由于实数的计算存在误差,当误差的量级不超过 10^{-6} 时,您的答案都将被接受。具体来说,设您的答案为 a ,标准答案为 b ,当且仅当 \frac{|a-b|}{\max(1,|b|)}\leqq 10^{-6} 时,您的答案将被接受。
示例1

输入

6
1 -1 3 2 -1 -2 1
2 -3 -1 3 1 0 0
3 0 3 -1 0 1 1
4 -4 2 2 0 -5 0
1 -4 2 2 0 -3 -1
2 -4 2 2 0 -3 -1

输出

-0.4 2.2
0.00000001
-0.5 1.5
2.2360679775
-2.2 1.4
2.5298221281347

说明

\hspace{15pt}样例一的位置关系如下图蓝色所示,样例二的位置关系如下图红色所示。

\hspace{15pt}样例三的位置关系如下图蓝色所示,其中,(0,3)(-1,0) 均是合法的答案;样例四的位置关系如下图红色所示。

发表于 2025-12-05 21:07:43 回复(0)