Ruins He's house

这题在 cnt 变量这里卡了好久，一直 WA 着，才发觉不对。、

和常规的题思路一致，查询的时候找到第一个 cnt 为 1 的结点就是解，注意 insert 函数 cnt 的更新必须更新 next 指针，root 单独更新，如果要到此结点了更新 cnt，那么最后的一个结点要更新 cnt，如果不更新会发生错误。

这题还是一样的题型，插入和查询，这次查询 find 函数中要注意的就是如果遍历到一个结点之后对应的 next 指针为空，就返回 0。

用 cnt 记录前缀出现次数，这时候就不用 danger 标记了。

本题思路和一般字典树有所不同，将全部的字符串读入离线处理，insert 操作和大部分字典树一致，接下来就是一个 dfs 函数，枚举全部字符串是否是符合条件的，dfs 的 tim 参数表示了这个是第几次查询，如果遇到 danger 标记，就可以有两种路径，继续本次查询和进入下一个查询，这样讲每一个字符串都判断完毕即可。

这题纠结了好久，之前没有考虑到 flag 标记，如果有如下的数据，之前的想法就错了:

1
2
3
4

1
2
00000
000

直接建字典树，注意一下几点：

1. 如果当前的结点是标记了 danger 的，那么就直接返回 false，表示有前缀。
2. 如果遍历到最后依然没有发现 danger 标记，要考虑这个结点有没有后继，如果有，说明他是某些结点的前缀，这个用 flag 标记。

自己在代码里加了一些注释，以便理解。

下午和队友一起做了下杭州赛区的比赛题，结果被虐了，只过了三题，两个队友没一会儿就开始打酱油。。。。实在受不了。

这道题裸的计算几何，求出多边形的重心，求重凸包，然后直接判断重心到凸包各点的投影是否在线段上，注意这里不用求出投影直接用点积即可，队友看错题 WA 了一次，我看了下图发现 90 的时候是不稳的。。。。到此整题就理论 AC 了，只要代码稳，可以轻松拿下。