100 + 0 + 0, 😅. 思之令人发笑。
T1
二分然后扫描线。
T2
判断一个点是否在一个简单环内，可以从这个点向上引一条竖线，竖线经过简单环边的数量为奇数则在环内，否则不在。
考虑找一个汇点，从每个点引出一条到汇点的边，使之形成一棵树。汇点找横坐标最小点即可，先求出一棵生成树然后以汇点为根即可。
那么简单环内点的数量即为 环 $\to$ 环外的边数 - 环外 $\to$ 环的边数，将每个点树上的邻点极角排序，产生的贡献是一段区间。
简单环按顺时针和逆时针排列是不同的，可以用叉积算面积来判断。
- 极角排序
atan2(y,x)返回 $(x,y)$ 与 $x$ 轴正方向的夹角。 - 叉积算面积 将其划分成三角形，三角形面积可以用叉积算。
另解
欧拉定理 $|V|-|E|+|F| = |C|+1$，图为连通图，只需求出面数和边数。
平面图转对偶图，对偶图删掉环对应的边，环围成的点所在连通块的点数为面数，边数为边数，线段树分治 + 可撤销并查集解决。
平面图转对偶图
将无向边拆为两条有向边，那么一条边对应一个面，对于边 $(u,v)$，将 $v$ 的所有出边按终点极角排序，找到 $(v,u)$ 的前一条边，那么 $(u,v)$ 和这条边同为下面面的边界，继续知道找到一个面即可，每条边标记所在面，对每个面建点，链接一条边和其反向边所在的面。判断是否为无界面可以叉积求面积。
T3
有向图，构造方案就是枚举边使得边的编号序列有连续的 $uv$，然后左右扩展。
考虑继续扩展合法路径，那么可以两条合法的通过 $0$ 拼一起，合法的和只缺一个的拼一起（可能顺序相反），只缺一个的也可以先初步预处理，然后就是只缺一个的和只缺一个的拼一起，相当于将初步的链视为边，然后边上转移。考虑 DP，$f_{i,j,0/1}$ 表示长度为 $i$，结尾为 $j$，缺不缺。按长度从小到大 DP，转移就是枚举初步的链，预处理出来即可，时间复杂度 $O(n^4)$。
总结
- 不会计算几何基础知识。