A. 新访问计划

B. 计算几何

其实题中这个常数 $c$ 的定义很奇怪，所以大概可以猜想，对于所有的情况都是有解的。

然后有这样一个做法，考虑弄一条直线出来，然后把 $n$ 条线段的对应端点都映射到这条直线上。

比如坐标系上的点 $(x,y)$ 映射到倾斜角为 $a$ 的直线上，可以认为坐标是 $x*\cos a +y*\sin a$。

考虑映射到直线上的每对左右端点的距离，即 $dis_{A,B}*\cos a$，这个玩意在期望情况下恰好等于常数 $c$。

然后就得到了 $n$ 个左端点和 $n$ 个右端点，因为两个点在二维平面上的距离要大于等于映射到的直线上的距离。

所以只要构造出一种不相交的方案来，就有超过 $\frac{1}{2}$ 的概率是合法的。

可以直接给这 $n$ 个左端点和 $n$ 个右端点分别视为二分图的左右部点，边权为两个点的距离，跑一个最小费用流最大流。

考虑如果有两条线段相交了，根据三角形不等式，交换会使费用更小，所以不存在相交的情况。

另外一个做法是个分治。

每次取点集的最靠左的点，然后以这个点为中心点，所有的点进行极角排序。

然后只要选择另外一个点，满足这个点与中心点颜色不同，这个点的两侧都满足 左端点数=右端点数 即可，容易发现这样总能构造出一种合法方案。

然后这个玩意的期望复杂度是 $O(n log^2)$ 的，肯定是能卡的（或许旋转下角度+小数据范围也卡不住）。

C. 树形图求和