1007. 简单几何题

题目描述

小 D 生活在被无尽海洋覆盖的星球上。由于行星所处的恒星系统引力极其混沌，它的自转轴和公转轨道处于极度的不稳定状态。这导致太阳光直射的方向都是完全随机的。行星的表面可以被视作三维欧几里得空间中的单位球面 S 2 =

{(x, y, z) ∈ R3: x2 + y 2 + z 2 = 1}。连接球面上任意两点（不为对跖点）的大圆上的劣弧，被称为短大圆弧。

这颗星球上仅有一块古老且连续的大陆 P，P 是一个球面简单多边形。它是由 n 条短大圆弧首尾相连构成的闭合区域，其边界不自交。同时，这块大陆整体被严格包含在某个开半球之内。当太阳光在星球上的直射点为 s 时，星球上处于白天的区域被定义为

Hs = {x ∈ S 2: s ⋅ x > 0}。界定白天与黑夜的大圆 s ⋅ x = 0 称为晨

昏线。为了在变幻莫测的气候中生存，小 D 致力于建立精确的行星气象模型。小 D 的核心任务是：在给定大陆形状与任意太阳直射点 s 时，计算这块大陆有多少比例的面积恰好沐浴在阳光之中。即求出以下百分比：

Area(P ∩ Hs )⋅ 100%Area(P )

球面面积：Area(P ) 指区域在单位球面上的表面积。在单位球上，一个边界大圆平面之间的二面角分别为 α, β, γ 的球面三角形，其球面面

积等于 α + β + γ − π，可结合上图理解。

输入格式

输入包含多组测试数据。第一行包含一个整数 T (1 ≤ T ≤ 500)，表示测试数据的组数。对于每组测试数据：第一行包含两个整数 n, q (3 ≤ n ≤ 500, 1 ≤ q ≤ 500)，分别表示大陆多边形的顶点数和查询的太阳方向数。接下来的 n 行，每行包含三个整数 x, y, z，表示多边形的顶点。第 i个顶点对应的实际球面坐标为 (

y,x2 +y 2 +z 2

x,x2 +y 2 +z 2

z)。x2 +y 2 +z 2

顶点按相对于球体外侧的逆时针顺序给出。接下来的 q 行，每行包含三个整数 x, y, z，表示一个查询的太阳直射点。对应的实际方向向量 s 为 (

xx2 +y 2 +z 2

,

yx2 +y 2 +z 2

,

zx2 +y 2 +z 2

)。

额外保证：

• 所有测试数据的 ∑ nq ≤ 5 × 106。

• 输入的所有坐标均满足 −105 ≤ x, y, z ≤ 105 且 (x, y, z) =

(0, 0, 0)。-

令 γ = 10−6 rad。对于多边形任意两个不同顶点 u, v，它们之间的球面距离 d(u, v) 满足 γ ≤ d(u, v) ≤ π − γ。

• 多边形边界不自交；相邻三点不共大圆；多边形总面积保证

Area(P ) ≥ 10−3。-

对于任意给定的直射点 s 和任意顶点 pi，保证点积 s ⋅ pi = 0，即

晨昏线不会穿过任何一个多边形顶点。-

存在向量 v 使得对任意 pi 满足 v ⋅ pi > 0，即多边形整体被包含

在某个开半球之内。

输出格式

本题使用 Special Judge 进行评测。对于每个查询，输出一行包含一个实数 r ∈ [0, 100]，表示白天部分占总面积的百分比。如果你的输出为 x，标准答案为 y，当且仅当满足∣x−y∣−6时，你的答案将被视为正确。max(1,∣y∣) ≤ 10

样例输入

1
4 2
10 0 10
0 10 10
-10 0 10
0 5 10
0 -10 3
0 10 -3

样例输出

16.37693771831994469373
83.62306228168005500789

提示

下图为样例的俯视示意图，青色分界线为晨昏线（两次查询的方向恰好相反）。其中，深色区域为第一次查询对应的白天部分，而浅色区域为第二次查询对应的白天部分。

该多边形总面积的精确形式为 4 arctan ( 10+32 10 )。

第一次询问所对应的区域面积的精确形式为9 2)。4 arctan ( 274+85 10+2879+10 790

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第1场）