CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:alchemist:pku_campus_2017 [2020/05/07 16:57]
mountvoom [B. Tiling Dominoes]
+++ 2020-2021:teams:alchemist:pku_campus_2017 [2020/05/08 22:40] (当前版本)
hardict [C. Skating on Weiming Lake(补题)]
@@ 行 8: / 行 8: @@
 ===== cmx  =====
 ===== lpy  =====
+计算几何还需加强(C题)
+要选择正确的容器以及判断是否快读(E题)
 ===== xsy  =====
+构造题做的太慢了，规律应该能更早看出来，分类讨论的时候一定要注意全面。
+WA的有两发都是因为自己太愚蠢了，$(1, 2)$和$(2, 1)$都输出了$AA$，还有一次没有删调试信息qwq，建议#ifdef。
 ====== 题解  ======
@@ 行 58: / 行 67: @@
 接下来在此基础上进行改进。
+$m$为偶数时，需要满足$n > 4$且$m > 4$，需要注意的是$n = 5, m = 6$有解，$n = 6, m = 6$无解。
+若此时$n$为偶数，则先按照$(m - 1, n)$构造，然后添加一列，这个部分比较简单不再赘述。
+若此时$n$为奇数且$n > 5$，可以使用刚才$m$为奇数的构造方式。
+最后就只剩下$m$为偶数，$n = 5$的情况，$n = 5, m = 6$的一个解如下：
+<code cpp>
+AABBAB
+BCCDAB
+BABDCC
+CABAAB
+CDDCCB
+</code>
+接下来不断改造右下角并一直扩展即可，比如$n = 5, m = 8时$解如下：
+<code cpp>
+AABBABEE
+BCCDABFF
+BABDCCGG
+CABAAHHJ
+CDDCCIIJ
+</code>
 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 =====

CVBB ACM Team

用户工具

站点工具

页面工具