2010 Multi-University Training Contest(12)
比赛中只做了那个关于圆的几何题，其他的都是队友做的。
How many times
题目大意：给平面上一些圆，求出覆盖次数最多的区域，输出次数。
我的做法：因为题目中说圆数目最多100个，所以我先将每两个圆的交点求出存起来，然后对每一个交点判断它在多少圆中，那么就可以得到这个点所在区域的覆盖最大次数，因为交点是各个区域交集的边缘。
然后对于不相交的情况：
枚举每个圆，统计有多少圆完全在它里面，取一个最大值，然后与上面相交情况比较取最大值，两者不会冲突，因为对交点处理的时候判断的是在圆内，那就把包含的加上了。
总结：比赛时候遇到两个问题：一开始我提问一个点算不算一个被统计的区域，回答说“No，it’s just a
point.”我就把一开始的做法（上面的那个）换掉了，开始往扫描线上面考虑，后来也不对，发现过的人越来越多，看了一下提问区，有人问同样的问题，居然回答是“Yes”。。囧。。。于是按原来的想法写，交了WA。。后来一番折磨之后队友突然出了一组数据，卡掉了。。原来是内含的情况不等式只写了一半，另一半没判断出来。。以后要认真啊！
赛后做的题：
Frost Chain
题目大意：给出5个英雄的位置，以及初始血量，现在有一个技能，初始打到每个英雄是等概率的，而且打到的话损失一点体力，接下来这个技能会继续弹到别的英雄那，一直下去直到次数的上限，每次它能弹到的英雄必须在一个距离范围内，而且对他们每个人都是等概率的。现在问题是求出每个英雄死的概率。
我的做法：用一个八维数组：dp[a][b][c][d][e][now][nowd][turn]
表示当前五个人体力依次是a、b、c、d、e，而且当前技能在now这个人身上，第turn次，nowd这个英雄死亡的概率，然后按照条件记忆化搜索就可以了。
总结：DP是我的弱项，dota更不会，所以这题对我来说是挑战。。。
Easy Geometry
题目大意：给出平面上的一些点，以及选择它们的概率，求出这些点构成的凸包的点数的期望。
我的做法：看了解题报告，想了一阵，问了luzilon学长，然后才明白。问题可以转化为求每个点出现在凸包上的概率的和。
每个点出现在凸包上的概率可以这样做：对每一个顶点，让其他顶点对该顶点进行极角排序，然后枚举剩下点作为该顶点在凸包中的邻接点，那么这样就有了凸包中的一条边了，这个点在凸包上的概率等价于这条边在凸包上的概率，也就是要将点集从被选的邻接点开始按照极角序扫描，180度以内的全都不选的概率就是这条边作为凸包边的概率（凸包的性质），这样每次只算半边，防止后面计算的重复。最后还要加上全不选的概率，只有一个自己这点。
总结：觉得是很好的一道题。学到不少，思路很好啊这题。