2020-2021:teams:wangzai_milk:weekly15

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:weekly15 [2020/08/14 17:08]
zars19 [团队训练]
+++ 2020-2021:teams:wangzai_milk:weekly15 [2020/08/14 18:25] (当前版本)
zars19 [比赛]
@@ 行 39: / 行 39: @@
 ==== 题目 ====
+无。
 ==== 比赛 ====
-◉ Codeforces Round #662 (Div. 2)
+◉ Codeforces Round 662 (Div. 2)
-◉ Codeforces Round #663 (Div. 2)
+◉ [[Codeforces Round 663 (Div. 2)]] **DONE**
-◉ Codeforces Round #664 (Div. 1)
+◉ Codeforces Round 664 (Div. 1)
 ◉ AtCoder Grand Contest 047
 ===== 本周推荐 =====
 ==== Infinity37 ====
@@ 行 85: / 行 85: @@
 **comments**：一个原根的经典用法，需要掌握。
+==== Zars19 ====
+**来源**：CF1388E - Uncle Bogdan and Projections
+**tag**：计算几何，Convex Hull Trick
+**概述**：
+给 $x$ 轴以上的若干水平线段。现可以指定一个向量让所有线段沿该方向投影到 $x$ 轴上，投影不可以重叠，宽度定义为投影最右端横坐标减去最左端横坐标，问可能的最小宽度。
+**答案**：
+如果纵坐标全部相同，直接垂直投影即可。否则我们可以在使得某个投影与投影相切的时候取到最小宽度。对任意两个纵坐标不同的线段，我们可以算出两个投影相切的角度，从而得到一段不可行的区间。扫描线得出全局的可行投影角度区间。
+而要在合理时间内得到取若干角度时投影的最大最小横坐标，可以用一个叫Convex Hull Trick的做法。设 $\theta$ 为投影线与 $x$ 轴正方向的夹角， $(x,y)$ 投影在横坐标 $x-\frac y{tan(\theta)}$ 的位置。以 $-\frac 1{tan(\theta)}$ 为自变量，则 $y_i$ 为斜率， $x_i$ 为截距。若干直线只会在一个凸包上取得最大值，我们先求出这个凸包，之后对于每个 $-\frac 1{tan(\theta_i)}$ 可以二分。最小值同理。
+**comments**：Convex Hull Trick可以适用在很多题上><

2020-2021/teams/wangzai_milk/weekly15.1597396084.txt.gz · 最后更改: 2020/08/14 17:08 由 zars19