北京培训 DAY1
早上考试 下午讲课 感觉挺累的
考试：
第一题
给定一系列对于点的操作 包括旋转与平移 询问一个点（0，0）在应用Ql到Qr这些变换后得到的点
矩阵+线段树 或者矩阵+逆矩阵 再或者分块+矩阵
平移矩阵为3*3的 旋转矩阵为2*2的 于是对平移建立矩阵
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| Δx | Δy | 1 |
对于旋转建立矩阵
| cosα | sinα | 0 |
| -sinα | cosα | 0 |
| 0 | 0 | 1 |
然后我们再以[x,y,1]去乘他们 最后得到的[x＇,y＇,1]中的x＇，y＇就是答案。
第二题 在一堆平面点中求一个包含k个点（其中必须包括x坐标y坐标字典序最小的点）的周长最大的凸包
n，k小于100的时候 我们可以先求出凸包 然后用DP求解 f[i][j]表示到达i这个点经过j个点的最长距离
f[i][j]=max(f[k][j-1]+dist(k,i))(k=1...i)
可惜数据范围是n,k<=1000 就需要有DP优化 然后出题人很高兴的告诉我们要用一个%^$%^#@%&$&办法去优化（反正我没听懂） 然后告诉了我们出自一篇名为Finding extremal polygons论文（下过来后发现这英文论文全看不懂）然后...再见
第三题 有生之年第一道提交答案题
给一张01图 让找出其中最大的圆的坐标以及半径
我写了一个半小时的各种程序乱搞 才弄出两个点 后来发现zhuohan1234在用肉眼对着数据乱搞 还弄出了8个点（Orz zhuohan1234）人都气傻了= = 最后出题人告诉我们正解就是乱搞 先用程序给原数据降噪 再用bmp 用gdi 用ps什么的开始肉眼乱搞 = =
。。。。。。
于是提交答案题给我留下了不可磨灭的不良印象
下午的讲课（据说是随机化）怎么都听不懂啊
一开始就先讲了bitcoin的工作原理 之后就开始讲 丧心病狂卡hash 随机化 hash 最小圆覆盖 随机增量法 最近点对 凸包（2D+3D） voronoi图 Delaunay三角剖分 所有圆是否有交点（随机增量 扫描线二分） 查询点所属区间 扫描线+平衡树（在线主席平衡树） &%￥%/&￥#*@@*&+%*......
人类们为何创造出了这么多奇奇怪怪丧心病狂的东西啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！！！！！
就这样吧
