[Div1][Div2]「CodePlus 2018 4 月赛」白金元首与七彩魔法

[Div1][Div2]「CodePlus 2018 4 月赛」白金元首与七彩魔法
给定HSV色盘上的两个点,求联结它们的直线段上亮度最大的颜色,精确到四位小数。
按照给出的公式,RGB值和极坐标的两个分量呈分段线性关系,亮度和RGB值呈线性关系。
将两点的极坐标转为直角坐标,等距离采样,按照公式计算,取最小值即可。
由于色盘上临近颜色的亮度值相近,精度不难得到保证。
关于采样数目的选择,比赛期间当然只要糊一个 10^5 就能过啦,不过这里随意证明一个极其松的上界聊博一笑吧
考虑一个与原点 O 距离为 r 的点 P,以其为端点任作一条不跨越 60\degree 分界线、长度为 d 的线段 PQ。此处 d 很小。
\theta 为线段 OP 与线段 OQ 张成的角,由于 \sin \theta \sim \theta,有 \theta \leq \frac d r
s = \lvert OQ \rvert,显然 \lvert r - s \rvert \leq d
由题目中给出的公式,有

于是我们证明了色盘上任何位置任何方向相当小的距离 d 以内颜色的亮度值与其相差不超过 2d,因而要达到 10^{-4} 的精度,只需间隔 10^{-4} 采样(即,将任意线段分成 2 \times 10^4 段)即可保证舍入后的正确性。不过由于精度误差,实际需要略高于此数量的采样点。
当然分成数百段之后分别三分也是可以达到本题要求的精度的。

发表评论

电子邮件地址不会被公开。 必填项已用*标注