原创 今天的baidu复赛题（争取3年之内看懂，汗……）

1. 验证码识别 (100分)
问题背景
Baidu的论坛抓取机器人小A，最近的抓取表现越来越差了。工程师小明发现原来是很多论坛需要注册才能浏览，而且在注册的时候需要填验证码。如图所示

于是小明准备升级小A机器人，让它能够自动识别验证码。
你能帮助小明设计识别验证码的程序吗？
为了控制开发难度，这个版本只需要识别 ！@#￥%&*-+ 九个符号即可。
我们已经为你将图片拆分成 100*100个点的位图，每个位图只包含一个符号，如下图所示的符号&。

同时为了让这个过程更有趣一点，我们将程序设计成交互式的，即你的程序向测试程序提问，通过测试程序的回答收集信息，当信息足够的时侯输出解答即可。

例如：（注意 “_”代表下划线，而不是空格 ）
提问: 你的程序向stdout 输出字符串 Q_1_3\n ，代表查询坐标（1，3）点的黑白信息；
回答: 测试程序向你的程序的stdin写入 P_1_3_0\n ，代表（1，3）点的颜色为白，同理，如果你的程序读到 P_1_3_1\n，代表（1，3）点的颜色为黑；
1 和 2 步骤不断循环，经过若干次交互，你的程序已经找到了答案，则可以输出结果：你的程序向stdout输出 R_&\n，测试程序就会记录识别结果和询问次数并退出测试。
测试程序
我们准备了一个帮助你测试的客户端程序，点击下载 Test.zip，需要的jre版本是 1.6.0_05。

注意
识别单个图片，询问次数超过2500次则不得分，识别正确，且询问次数分数不高于500次得全分，高于500次后分数线性递减；
识别单个图片，交互总时间超过15s则不得分；
识别结果正确得30%的分数，识别结果错误不得任何分数；
所有测试图形都由同一个出题人书写，字体方向正放向上；
尺度不小于50像素，即主体符号无噪声包围盒的长宽不同时小于50像素；
图片随机噪声点比例不高于15%，图片上的黑白点都有可能随机翻转，而在添加噪声的过程中我们已经保证主体符号的含义是确定的；
Test.zip 中的测试数据是无噪声的，与评测数据不同，请特别注意。

2.度度熊吃西瓜

和其它熊不同，度度熊最喜欢吃的东西是西瓜，但是西瓜有一个很让它讨厌的地方--有很多的籽儿。可怜的度度熊并不知道这个世界上原来还有无籽西瓜这个东西。度度熊是一只很懒很懒的熊，并且它以Larry Wall的名言作为自勉--懒是一种美德。它吃西瓜从不吐籽儿--因为太麻烦了。当然，这种美德是有代价的，度度熊经常因为吃西瓜籽闹肚子。

有一天，这只懒熊突发奇想--如果能用一刀把那些籽儿全部切掉该多爽啊（当然，秉承懒的美德，切两刀是很辛苦的）。度度熊有一个很奇怪的仪器，可以检测出西瓜籽儿的坐标位置。于是度度熊立马动起手来（对于这种事，它一点都不懒）。但是它很快就发现，如果刻意追求切出的西瓜块儿不带籽儿，那它能吃到的西瓜就只有很少的一点了，这真是一件很扫兴的事。于是，它就只好作了个让步，只要切剩下的西瓜部分包含的籽儿的个数不大于给定的值m就可以接受，这个m究竟是多少要取决于度度熊的心情和食欲。

可是度度熊的几何学得太差了，面对那些坐标它不知该用哪个公式去算，它只好求助于你--聪明的程序员了。

度度熊吃的西瓜的形状比较特殊，它看起来像这样子：

这看起来像个扁平的扇形，为了减轻你的负担，你可以将这个问题近似成一个平面的问题。西瓜是一个圆面的一部分，并且面积严格小于整个圆面的一半，最上面的顶点就是圆心。

给出西瓜的形状和籽儿的坐标，你的任务是求一个最佳的切割位置（刀面是直的），使得切出来的一块西瓜包含的籽儿不大于给定的数m，含不含有西瓜皮都没有关系－度度熊不讨厌吃西瓜皮。在这样的条件下当然是要求切出来的部分尽可能大了（度度熊现在很饿）。由于已简化为平面问题，所以你的任务是输出吃到的部分的面积。
注意：你可以忽略西瓜皮和西瓜籽的大小。

所有的坐标以极坐标格式输入。具体的格式是 (ρ,θ)，分别表示（极径，极角），极角以角度为单位，圆心在极点。
其中 0＜ρ, 0≤θ＜360

名词解释
极坐标
在平面内取一个定点O， 叫极点，引一条射线Ox，叫做极轴，再选定一个长度单位和角度的正方向(本题取逆时针方向)。对于平面内任何一点M，用ρ表示线段OM的长度，θ表示从Ox到OM 的角度，ρ叫做点M的极径，θ叫做点M的极角，有序数对 (ρ,θ)就叫点M的极坐标，这样建立的坐标系叫做极坐标系。

输入格式
第一行一个正整数T，说明共T组数据，T ≤ 10。
第二行一个正整数r，说明西瓜的半径是r，r ≤ 106。
第三行一个非负整数m，说明度度熊能够忍受的西瓜籽的个数为m， m ≤ 1000。
第四行两个非负整数 a, b，分别是西瓜皮的两个端点的极角，0 ≤ a < b < 360, 0 < b - a < 180。
第五行一个非负整数n，表示西瓜里头有n个籽儿，n ≤ 1000。
接下来的n行表示n个籽儿的坐标。每行两个整数表示（极径，极角），籽儿保证在西瓜内，但可能在边界上。

输出格式
对每一组数据，输出单独一行，表示度度熊能切出来＂包含不大于m个籽儿的西瓜片＂的最大面积(四舍五入到小数点后5位)。

样例输入
2
10
1
0 90
2
1 45
7 45
10
0
0 90
2
1 45
7 45

样例输出
77.53982
39.26991

3.黑白树 (100分)
问题背景
 在图论中，包含n个结点（结点编号为1~n）、n-1条边的无向连通图被称为树。
在树中，任意一对结点间的简单路径总是惟一的。
你拥有一棵白色的树--所有节点都是白色的。接下来，你需要处理c条指令：

修改指令(0 v)：改变一个给定结点的颜色（白变黑，黑变白）；
查询指令(1 v)：询问从结点1到一个给定结点所经过的第一个黑色结点编号（假设沿着简单路径走）。
注意，在查询指令中，必须从结点1而不是结点v出发。如果结点1本身就是黑色，查询指令应该返回1。

输入说明
第一行包含两个正整数n, c，即结点数和指令条数。
以下n-1行，每行两个正整数(ui, vi) (1 <= ui < vi <= n)，表示结点ui到vi之间有一条无向边。
以下c行，每行两个整数(c, v)。当c=0时表示修改指令，其中v代表被修改的结点编号；c=1时表示查询指令。
你的程序需要输出结点1到结点v之间路径的第一个黑色结点编号。
在第一条指令执行前，所有结点都是白色的。

输出格式
对于每个查询操作(c=1的操作)，输出一行，包含一个整数，即第一个黑色结点的编号。如果不存在黑色结点，输出-1。

样例输入
9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
1 3
0 8
1 6
1 7
0 2
1 9
0 2
1 9

样例输出
-1
8
-1
2
-1

评分说明
共有30个数据，分为3组，按组计分。这三组的满分分别为20, 30, 50分。
第一组: n="5000", m="4000000"
第二组: n="100000", m="3000000"
第三组: n="1000000", m="1000000"
每组数据中只要有一个数据运行超过5秒或者答案错，该组计0分。
否则，该组数据的得分取决于其中运行时间最长的数据的运行时间：运行时间越短，得分越高。