#P14866. [OOI2025 资格赛]Colorful Diameter彩色直径

    ID: 14082 传统题 7000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-凸性/单峰性判定二分查找分治算法Andrew 算法Minkowski 和凸多边形边向量归并合并有序结果平方距离比较叉积

[OOI2025 资格赛]Colorful Diameter彩色直径

题目描述

平面上有 nn 个点,点 ii 的坐标为 (xi,yi)(x_i,y_i),颜色为 cic_i。每个点以恒定速度沿向量 (dxi,dyi)(dx_i,dy_i) 运动。也就是说,每经过一秒,点 ii 的横坐标增加 dxidx_i,纵坐标增加 dyidy_i。

对于前 TT 秒中的所有整数时刻,求不同颜色点之间最大距离的最小值。

换句话说,需要找到一个整数时刻 tt(0≤t≤T0\le t\le T),使得在该时刻,不同颜色点对之间的最大距离相比其他所有整数时刻最小。

输入格式

每个测试包含多组数据。

第一行包含一个整数 tt(1≤t≤1000001\le t\le 100000),表示数据组数。

接下来依次给出每组数据。

每组数据第一行包含两个整数 n,Tn,T(2≤n≤2000002\le n\le 200000,0≤T≤1080\le T\le 10^8),分别表示点的数量和考虑的时间区间。

接下来 nn 行描述点。第 ii 行包含五个整数 xi,yi,dxi,dyi,cix_i,y_i,dx_i,dy_i,c_i(−108≤xi,yi,dxi,dyi≤108-10^8\le x_i,y_i,dx_i,dy_i\le 10^8,1≤ci≤n1\le c_i\le n),分别表示点的坐标、两个坐标方向的速度以及点的颜色。

保证至少存在两个颜色不同的点。

保证每个测试中所有数据组的 nn 之和不超过 200000200000,所有数据组的 TT 之和不超过 10810^8。

保证任意点在 00 到 TT 的任意时刻,其坐标绝对值不超过 10910^9。

输出格式

对于每组数据,输出一行一个数,表示前 TT 秒中不同颜色点之间最大距离的最小值。

若答案的绝对误差或相对误差不超过 10−910^{-9},则认为正确。

形式化地,设你的答案为 aa,标准答案为 bb,当且仅当

∣a−b∣max⁡(1,∣b∣)≤10−9\frac{|a-b|}{\max(1,|b|)}\le 10^{-9}

时答案会被接受。

样例

3
3 0
1 1 0 0 1
2 2 0 0 2
4 4 0 0 1
2 2
0 0 1 1 1
2 2 -1 -1 2
4 100
0 0 0 1 1
4 0 -1 0 2
4 4 0 -1 1
0 4 1 0 2
2.82842712474619009753
0.00000000000000000000
2.82842712474619009753

样例解释

第一组数据中,只考虑一个时刻。第一点与第二点距离为 2\sqrt{2},第二点与第三点距离为 222\sqrt{2},因此答案为 222\sqrt{2}。

第二组数据中,在时刻 11,两个点重合,因此不同颜色点之间距离最大值为 00,答案为 00。

第三组数据中,可以证明不同颜色点之间最大距离的最小值在时刻 22 取得,值为 222\sqrt{2}。

第三组数据在 t=0,1,2t=0,1,2 三个时刻的状态,其中颜色 11 的点用红色标记,颜色 22 的点用蓝色标记:

评分方式

本题测试点由 9 个分组组成。只有通过某一组及其要求的部分前置分组时,才能获得该组分数。注意,部分分组不要求通过样例。Offline-testing 表示该组测试结果只会在比赛结束后给出。

设 ∑n\sum n 为当前测试中所有数据组的 nn 之和,∑T\sum T 为所有数据组的 TT 之和。

组别 分数 附加限制:∑n\sum n 附加限制:∑T\sum T 依赖分组 说明
0 - 样例
1 10 ∑n≤100\sum n\le 100 ∑T≤10\sum T\le 10 0 -
2 8 ∑n≤10000\sum n\le 10000 0,1
3 11 ∑n≤100\sum n\le 100 -
4 14 ∑n≤100000\sum n\le 100000 ∑T≤10\sum T\le 10 - 恰好有 2 种不同颜色
5 8 - 4
6 11 ∑T≤10\sum T\le 10 - 所有颜色互不相同
7 8 - 6
8 19 0–7 -
9 11 - 0–8 Offline-testing