话说省队集训居然开放所有人参加，于是参加的人远远不止15个……
作为高一参加省队集训的蒟蒻WAer……
自然是被神犇们爆虐咯……
Day1
计算几何。
居然有两道省冬原题，所以今天训练并没有什么卵用。
一堆人高分。
然后我有一道原题被卡精度，WA了50分。
坐等本WAer明天继续爆炸= =
Day2
计算几何。完全写不动的东西。
上午讲了各种凸包、半平面交、旋转卡壳之类的东西，由于我是口胡选手所以自然以为都会了2333
然而下午的测试让我明白了我是多么的naive。
第一题：给 $n$ 个平面 $xOy$ 上的动点（保证不存在始终重合的），时刻 $t$ 第 $i$ 个动点位置 $(kx_i\cdot t+bx_i,ky_i\cdot t+by_i)$，$i$，$j$ 连一条边当且仅当存在 $t\in(-\infty,+\infty)$，求图的最大团。
一眼看没什么思路，先敲了个 $O(2^nn)$ 暴力。
第二题，平面上有两个点集 $A$，$B$，$A\cup B$ 内没有三点共线，每个 $B$ 中的点 $i$ 有 $p_i$ 概率选，$1-p_i$ 概率不选，求选出的点的凸包内 $A$ 中的点个数期望值。
想了下不知道能不能用期望的性质搞，但很快被我叉掉了。
算了先弃这一题。
第三题，给两个点集 $A$，$B$，求顶点都在 $A$ 中的最大凸多边形使得其内部没有 $B$ 中的点。输出方案。
……这不是原题吗？虽然我当时也没做出来不过我会做，哈哈。
不过似乎挺难写？算了回去看第一题。
第一题研究了挺久，推了个式子 $\frac{ky_i-ky_j}{kx_i-kx_j}=\frac{by_i-by_j}{bx_i-bx_j}$ 但并没有什么卵用。
想了想决定加个垂直于 $xOy$ 平面的 $t$ 轴，于是变成三维空间求两两相交的直线集。
看样子这些线共面，于是枚举两条线确定平面然后统计平面上的线，呼……终于写完了……
接着开始搞第三题。
排序以后可以DP，开始写各种情况。
一写两三个小时过去了……
终于写完，样例过不了，又调了好久才过样例。我代码能力该是有多弱啊= =
由于省队集训名义上比赛时间是5h，实际上只有4.5h，只剩下半个小时左右了。
赶紧敲第二题暴力。
敲完了。
第一题对拍没问题。然而这题随机数据几乎答案都是1和2，对拍并没有什么卵用。
结果意识到一个问题——
不仅可能所有线共面，还有可能所有线不共面但共点！
觉得要改很麻烦，没时间改了。再说也许数据弱呢
第三题出了一组数据WA了，又改了几个地方才过。要结束了，没时间对拍了。感觉这下没问题了
完了似乎要跪了。。。
开始评测，结果……
鄂公网安备 42010202000505 号