2020-2021:teams:alchemist:pku_campus_2017
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:pku_campus_2017 [2020/05/08 16:41] hardict [lpy] |
2020-2021:teams:alchemist:pku_campus_2017 [2020/05/08 22:40] (当前版本) hardict [C. Skating on Weiming Lake(补题)] |
||
|---|---|---|---|
| 行 96: | 行 96: | ||
| by MountVoom | by MountVoom | ||
| - | ===== C. Skating on Weiming Lake ===== | + | ===== C. Skating on Weiming Lake(补题)===== |
| + | **题意:** | ||
| + | |||
| + | 圆中两个点,找个圆在圆内且不含两点 | ||
| + | |||
| + | **题解** | ||
| + | |||
| + | 首先考虑单点,即考虑找一个最大的圆不包含一个点 | ||
| + | |||
| + | 易知为该点$P$与圆心$C$构成的射线$\overrightarrow{PC}$与圆交于$F$,以$PF$为半径的圆$\Gamma$ | ||
| + | |||
| + | 判断另一点$Q$是否在$\Gamma$中即可 | ||
| + | |||
| + | <code cpp> | ||
| + | ans = P + (C - P).unit() * (C.len(P) + R) * 0.5; | ||
| + | if (dcmp(ans.len(P), ans.len(Q)) <= 0) { | ||
| + | flag = true; | ||
| + | ansR = ans.len(P); | ||
| + | } | ||
| + | </code> | ||
| + | |||
| + | 而如果$P,Q$两点单点构造出的圆都不满足,考虑由两点一起进行构造 | ||
| + | |||
| + | 分析可得圆心$D$应该在$PQ$垂直平分线上,且与圆$C$相切于$G$ | ||
| + | |||
| + | $r=DP=DQ=DG,DG=R-r,DP+DG=R$,$设f(D)=DP+DG在垂直平分线上应该是至多存在两点D_{1},D_{2},s.t\quad f(D_{i})=R$ | ||
| + | |||
| + | 且$f(D)$是单峰的 | ||
| + | |||
| + | 考虑对$f(D)$进行三分,找到峰值$D_{0}(为最小值)$,然后二分得到$D_{i}$ | ||
| + | |||
| + | <code cpp> | ||
| + | Point E = (P + Q) * 0.5; | ||
| + | Vector vertical = (P - Q).unit().rotate(); | ||
| + | // E.print(); | ||
| + | // vertical.print(); | ||
| + | double l = -4e9, r = 4e9; | ||
| + | while (dcmp(l, r) == -1) { | ||
| + | double a, b; | ||
| + | a = (2 * l + r) / 3, b = (l + 2 * r) / 3; | ||
| + | Point A, B; | ||
| + | A = E + vertical * a, B = E + vertical * b; | ||
| + | if (dcmp(A.len(P) + A.len(C), B.len(P) + B.len(C)) > 0) | ||
| + | l = a; | ||
| + | else | ||
| + | r = b; | ||
| + | } | ||
| + | double extremepoint = (l + r) / 2; | ||
| + | // Point X = E + vertical * extremepoint; | ||
| + | // X.print(); | ||
| + | // printf("%.8lf\n", X.len(P) + X.len(C)); | ||
| + | l = extremepoint, r = 4e9; | ||
| + | while (dcmp(l, r) == -1) { | ||
| + | double mid = (l + r) / 2; | ||
| + | Point A = E + vertical * mid; | ||
| + | if (dcmp(A.len(P) + A.len(C), R) > 0) | ||
| + | r = mid; | ||
| + | else | ||
| + | l = mid; | ||
| + | } | ||
| + | Point tmpans = E + vertical * ((l + r) / 2); | ||
| + | |||
| + | l = -4e9, r = extremepoint; | ||
| + | while (dcmp(l, r) == -1) { | ||
| + | double mid = (l + r) / 2; | ||
| + | Point A = E + vertical * mid; | ||
| + | // A.print(); | ||
| + | if (dcmp(A.len(P) + A.len(C), R) > 0) | ||
| + | l = mid; | ||
| + | else | ||
| + | r = mid; | ||
| + | } | ||
| + | ans = E + vertical * ((l + r) / 2); | ||
| + | if (dcmp(ans.len(P), R) == 1) | ||
| + | ans = tmpans; | ||
| + | else if (dcmp(tmpans.len(P), R) <= 0 && | ||
| + | dcmp(ans.len(P), tmpans.len(P)) <= 0) | ||
| + | ans = tmpans; | ||
| + | ansR = ans.len(P); | ||
| + | </code> | ||
| + | |||
| + | 特别注意预处理等于圆心的点 | ||
| + | |||
| + | <code cpp> | ||
| + | Point P(x, y); | ||
| + | if (P == C) P = P + Point(eps, -eps); | ||
| + | </code> | ||
| + | |||
| + | by Hardict | ||
| ===== D. Travel to Qomolangma ===== | ===== D. Travel to Qomolangma ===== | ||
2020-2021/teams/alchemist/pku_campus_2017.1588927301.txt.gz · 最后更改: 2020/05/08 16:41 由 hardict
