原题链接：M. Ordainer of Inexorable Judgment

题目大意

在二维平面上有一从坐标原点发出的射线，初始方向给定，射线实际的范围包括为向垂直于射线的方向两端延申 $d$ 的距离。现按逆时针顺序给定一个凸多边形，射线转动速度为 $1rad/s$，求在 $t$ 时间内射线接触到凸多边形的总时间（题目保证该凸多边形与半径为 $d$，圆心在原点的圆没有交点）。

样例输入：
依次给出凸多边形的点数 $n$，初始朝向的向量 $(x_0,y_0)$，以及距离 $d$ 和总时间 $t$。

3 1 0 1 1
1 2
2 1
2 2

样例输出：

1.000000000000

题目分析

• 由于一个周期（即 $2\pi$ ）内一定与凸多边形相交一整次，将时间 $t$ 划分为 $k$ 个 $2\pi$ 和剩余的时间 $rem$。
• 考虑以下图片，倘若射线从凸多边形外移动到与凸多边形接触，射线最左侧先接触到多边形上的一个点且与半径为 $d$，圆心在原点的圆相切；当射线从凸多边形内移动到凸多边形外时，射线最右侧在最后接触到多边形上一个点且同样与圆相切。
  
• 对于凸多边形上每一个点，都有关于这样的一个圆的两条切线，根据几何关系，左/右两个切线的极角对应射线进/出凸多边形时的极角。将每个凸多边形上的点贡献两个极角存入数组 $avg$ 里，我们需要选出所有极角中最小角和最大角，但由于 $atan2$ 函数范围为 $(-\pi ,\pi ]$，需要规范化到 $[0,2\pi )$ 才更容易处理。现在考虑选出来的两个极角 $l,r$ 表示的范围是 $[l,r]$ 还是 $[0,l]\cup [r,2\pi ]$ 这个问题，由于问题保证了该凸多边形与半径为 $d$，圆心在原点的圆没有交点，那么两个极角的大小差距小于 $\pi$，故对于从小到大排好序的 $avg$，若该数组最后一个元素与第一个元素的差小于 $\pi$，则说明是 $[l,r]$ 这种形式；反之，我们需要找到 $avg[i]+\pi -avg[i+1]<0$ 的点，即 $avg[i]=l,avg[i+1]=r$。用 $flag$ 为 $true$ 表示后者跨越 $2\pi$ 这种情况，$false$ 表示前者那种情况。
• 当 $flag=false$ 时，最终答案为 $k\times (r-l)$ 加上从初始向量转动 $rem$ 时间内与凸多边形相交的时间之和；若 $flag=true$，我们同样按照前者的公式计算，但此时计算出来的是范围在 $[l,r]$ 之内的结果（与凸多边形不相交的结果），而真正的结果 $[0,l]\cup [r,2\pi ]$ 恰为该结果的补集，故最终答案为 $t-ans$。

代码答案

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;
const double eps = 1e-9;
const double PI = acos(-1.0);

int sgn(double x) {
    if(fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

double gcd(double x, double y) {return fabs(y) < eps ? x : gcd(y, fmod(x, y));}
double acos_(double x) {return acos(max(min(x, 1.0), -1.0));}
double asin_(double x) {return asin(max(min(x, 1.0), -1.0));}

// 点结构体
struct Point {
    double x, y;
    Point(){}
    Point(double x, double y) : x(x), y(y) {}
    bool operator ==(Point p) const {return sgn(x - p.x) == 0 && sgn(y - p.y) == 0;}
    void input() {cin >> x >> y;}
    void output() {cout << x << ' ' << y << endl;}
    bool operator <(Point p) const {return sgn(x - p.x) < 0 || (sgn(x - p.x) == 0 && sgn(y - p.y) < 0);}
    // 向量加法
    Point operator +(Point p) const {return Point(x + p.x, y + p.y);}
    // 向量减法
    Point operator -(Point p) const {return Point(x - p.x, y - p.y);}
    // 点积（内积）：向量A在向量B上的投影长度乘向量B的模长
    double operator *(Point p) const {return x * p.x + y * p.y;}
    // 数乘
    Point operator *(double k) const {return Point(x * k, y * k);}
    Point operator /(double k) const {return Point(x / k, y / k);}
    // 叉积（外积）：向量A与B张成的平行四边形的有向面积
    double operator ^(Point p) const {return x * p.y - y * p.x;}
    // 规范化极角：[0, 2π]
    double pangle() const {return (sgn(atan2(y, x)) < 0) ? atan2(y, x) + 2 * PI : atan2(y, x);}
    // 距离（模长）：向量A到向量B的有向距离
    double len(Point p = Point(0, 0)) const {return hypot(x - p.x, y - p.y);}
    // 角度（弧度制）：两向量无向夹角[0, π]
    double angle(Point p = Point(1, 0)) const {return acos(*this * p / len() / p.len());}
    // 角度（弧度制）：两向量有向夹角[-π, π]
    double dangle(Point p = Point(1, 0)) const {
        double delta = atan2(p.x, p.y) - atan2(x, y);
        while(delta > PI) delta -= 2 * PI;
        while(delta < -PI) delta += 2 * PI;
        return delta;
    }
    // 旋转（弧度制）：逆时针旋转theta弧度
    Point rotate(double theta) {return Point(x * cos(theta) - y * sin(theta), y * cos(theta) + x * sin(theta));}
};

const int N = 1e3 + 10;
double x, y, d, t;
int n;
Point p[N];

void solve() {
	cin >> n >> x >> y >> d >> t;
	vector<double> avg;
	Point st(x, y);
	for(int i = 1; i <= n; i++) p[i].input();
	for(int i = 1; i <= n; i++) {
		double phi = acos_(d / p[i].len()), cur = p[i].pangle();
		avg.pb((p[i] - Point(d, 0).rotate(cur + phi)).pangle());
		avg.pb((p[i] - Point(d, 0).rotate(cur - phi)).pangle());
	}
	double ang = st.pangle();
	for(int i = 0; i < 2 * n; i++) {
		avg[i] -= ang;
		if(avg[i] < 0) avg[i] += 2 * PI;
	}
	sort(all(avg));
	bool flag = true; // 表示 [0, avg[i]] [avg[i + 1], 2π]
	double l, r;
	if(sgn(avg[0] + PI - avg.back()) > 0) {
		l = avg[0], r = avg.back();
		flag = false; // 表示在 [l, r] 内部
	} else {
		for(int i = 0; i < 2 * n - 1; i++) {
			if(sgn(avg[i] + PI - avg[i + 1]) < 0) {
				l = avg[i], r = avg[i + 1];
				break;
			}
		}
	}
	double k = floor(t / (2 * PI));
	double rem = t - k * 2 * PI;
	double ans = k * (r - l);
	ans += max(0.0, min(r, rem) - l);
	// flag 为 true 代表原 ans 算的是射线与凸多边形不相交的总时间
	ans = (flag ? t - ans : ans);
	cout << fixed << setprecision(12) << ans << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

问题模型提取

问题模型：给定一条原点发出的射线及初始法向量，问在给定时间内，射线不断逆时针旋转，与一个凸多边形接触的时间。

问题难点：该模型主要难点在于凸包边界两点对应两极角 $l,r$ 所在范围的处理，若题目保证原点不被包裹在凸多边形内部，先将所有极角规范化到 $[0,2\pi ]$，那就分为以下两种情况。

• $l+\pi >r$，代表范围在 $[l,r]$ 内，没有跨过 $2\pi$，此时 $r-l$ 对应的是在一个周期内射线与凸多边形相交的时间。
• $l+\pi <r$，代表范围在 $[0,l]\cup [r,2\pi ]$，跨过了 $2\pi$，此时 $r-l$ 对应的是在一个周期内射线与凸多边形不相交的时间，用总时间减去不相交的时间即可。

伪代码示例：

// 前提条件：
// 1. 存在环形角度空间（范围 [0, 2π)，0 与 2π 重合）
// 2. 动态对象：绕原点逆时针旋转的射线（角速度 1 rad/单位时间，总时间 t）
// 3. 静态对象：凸多边形（不将原点包括在内）
// 4. 目标：计算 t 时间内，射线与凸多边形的接触总时间

function pangle(Point p):
	return atan2(p.y, p.x) + 2π if atan2(p.y, p.x) < 0 else atan2(p.y, p.x)


// 输入初始化
input n, x, y, t  // n:凸多边形顶点数，(x,y):初始朝向，t:总时间
st = Point(x, y)  // 初始朝向向量（从原点出发）
p = [Point(0,0) for _ in 1..n]  // 存储凸多边形顶点
avg = empty list  // 存储凸多边形上的点对应的极角

for i from 1 to n:
    input xi, yi
    p[i] = Point(xi, yi)
    avg[i] = pangle(p[i])

// 对齐初始朝向，统一角度基准
init = pangle(st)  // 初始朝向的极角
for i from 0 to len(avg)-1:
    avg[i] = avg[i] - init + 2π if avg[i] < init else avg[i] - init  // 对齐到初始朝向的局部坐标系

sort avg  // 排序边界角度，将环形问题线性化

// 判断区间类型（接触区间是否跨环形边界 0/2π）
l, r; flag = true  // 标记：true=接触区间跨 0/2π（[0,l]∪[r,2π]），false=接触区间不跨（[l,r]）

// 情况1：所有边界集中，接触区间不跨 0/2π（[l, r]）
if avg[0] + π - avg[len(avg)-1] > 0:
    l = avg[0]
    r = avg[len(avg)-1]
    flag = false
// 情况2：边界分散，接触区间跨 0/2π（[0,l]∪[r,2π]）
else:
    for i from 0 to len(avg)-2:
        if avg[i] + π - avg[i+1]) < 0:
            l = avg[i]
            r = avg[i+1]
            break


// 计算接触时间（分“完整周期”和“剩余时间”）
cycle = 2 * π  // 旋转周期（一圈的时间）
k = floor(t / cycle)  // 完整周期数
rem = t - k * cycle  // 剩余时间（不足一圈的部分）

// 中间结果：先计算“区间[l,r]与旋转过程的重叠时间”（可能是接触/非接触时间，由flag决定）
cycle_len = r - l  // 单个周期内，区间[l,r]的长度
total = k * cycle_len  // 完整周期的重叠时间

// 剩余时间的重叠时间（线性区间重叠计算）
total += max(0.0, min(r, rem) - l)  // 仅当 rem > l 且 rem < r 时才有重叠

// 修正结果（根据区间类型，得到真正的接触时间）
if flag:
    // flag=true：[l,r]是非接触区间，接触时间 = 总时间 - 非接触时间
    ans = t - total
else:
    // flag=false：[l,r]是接触区间，重叠时间就是接触时间
    ans = total