分类：
2008-06-16 17:24:09
2008年6月14日百度之星大赛在线复赛正式展开，400名入围选手在线一搏争取前50的总决赛资格。在第一时间给大家带了初赛题目，在这里我们还要感谢华南理工大学参赛选手陈同学友情提供。
1. 验证码识别
问题背景
Baidu的论坛抓取机器人小A，最近的抓取表现越来越差了。工程师小明发现原来是很多论坛需要注册才能浏览，而且在注册的时候需要填验证码。如图所示
于是小明准备升级小A机器人，让它能够自动识别验证码。你能帮助小明设计识别验证码的程序吗？为了控制开发难度，这个版本只需要识别 ！@#￥%&*-+ 九个符号即可。我们已经为你将图片拆分成 100*100个点的位图，每个位图只包含一个符号，如下图所示的符号&。
同时为了让这个过程更有趣一点，我们将程序设计成交互式的，即你的程序向测试程序提问，通过测试程序的回答收集信息，当信息足够的时侯输出解答即可。
例如：（注意 “_”代表下划线，而不是空格 ）
1. 提问: 你的程序向stdout 输出字符串 Q_1_3\n ，代表查询坐标（1，3）点的黑白信息；
2. 回答: 测试程序向你的程序的stdin写入 P_0\n ，代表（1，3）点的颜色为白，同理，如果你的程序读到 P_1\n，代表（1，3）点的颜色为黑；
3. 1 和 2 步骤不断循环，经过若干次交互，你的程序已经找到了答案，则可以输出结果：你的程序向stdout输出 R_&\n，测试程序就会记录识别结果和询问次数并退出测试。
测试程序
我们准备了一个帮助你测试的客户端程序，点击下载 ，需要的jre版本是 1.6.0_05，下载 。
注意
1.识别单个图片，询问次数超过2500次则不得分，识别正确，且询问次数分数不高于500次得全分，高于500次后分数线性递减；
2.识别单个图片，交互总时间超过15s则不得分；
3.识别结果正确得30%的分数，识别结果错误不得任何分数；
4.所有测试图形都由同一个出题人书写，字体方向正放向上；
5.尺度不小于50像素，即主体符号无噪声包围盒的长宽不同时小于50像素；
6.图片随机噪声点比例不高于15%，图片上的黑白点都有可能随机翻转，而在添加噪声的过程中我们已经保证主体符号的含义是确定的；
7.Test.zip 中的测试数据是无噪声的，与评测数据不同，请特别注意。
2. 寻找所有的同构象（图片及公式暂缺）
问题描述
三维空间中，为一个物体定义如下三种基本的变换：
平移：物体沿着一条直线α进行一段位移δ。对于物体中的任意一点，其起始位置和终止位置连成的线段平行于α，长度为δ。
反射：物体相对于一个平面β作镜像。对于物体中的任意一点，其起始位置和终止位置连成的线段垂直于β，并且到β的距离相等。
旋转：物体绕着一条轴线γ转过一定角度φ。对于物体中的任意一点，由其起始位置和终止位置对γ作垂线，垂足重合，垂线段长度相等，并且两条垂线所成的角度为φ。
物体A经过上述三种基本变换或基本变换的有限次组合，变成物体A’，若A’与A完全重合（对于空间中的任意一点，如果它属于A’，则一定属于A，反之亦然），则称A’为A的一个同构象。
需要注意的是，上面所说的物体和它的同构象并不一定是相同的物体，可以理解为物体上的每个点都是“有记号”的，虽然二者在形状、体积、位置上完全重合，但其中只要有一个点经过变换以后位置发生了改变，就是不同的物体。例如，线段u关于它的中垂面做反射得到线段v，虽然u和v在三维空间中重合，但u上的点变换到v以后位置发生了改变，所以u和v是不同的物体。
从定义出发，容易证明，同构象满足下面的3条性质：
1.自反性：A是A自身的一个同构象。
2.对称性：若B是A的一个同构象，则A是B的一个同构象。
3.传递性：若B是A的一个同构象，C是B的一个同构象，则C是A的一个同构象。
推论：若B是A的一个同构象，C也是A的一个同构象，则B和C彼此互为同构象。
B和C都是A的同构象，若有一个基本变换序列S把B变换到C，且满足对于任意点p属于B，S把p变换到p自身，则称B和C为相同的同构象。例如，线段u绕着中垂线旋转180度得到一个同构象v，还可以关于中垂面反射得到一个同构象v’，v和v’就是相同的同构象。
同构象的相同和不同是对本题非常重要的概念。事实上，由于B和C都是A的同构象，由上面的推论，B和C一定互为同构象，因此S是一定存在的。那么B和C相同的唯一要求就是S把B变换到B自身，其实同构象“相同”的本质就是B=C。
A的全部不同的同构象组成的集合叫做A的同构象集。例如，上面所举的线段的例子中，u的同构象集就是{u,v}。
又例如，一个正三棱锥的同构象集共有6个元素，分别沿中轴旋转0、120、240度得到其中3个，再沿图中的β平面做反射以后，同样旋转又得到另外3个，这6个同构象集中的元素任意两者都不相同：
题目输入一个凸多面体的所有顶点坐标，要求输出这个凸多面体的同构象集所包含的元素个数。
输入的点至少有4个，每个输入作为一个顶点可以唯一确定一个多面体。不需要考虑非凸的情况，不需要考虑多点共线的情况，也不要求处理所有点退化到一个平面多边形的情况。但是有可能存在4个或以上的点共面。
多点共面的判断规则如下：四个点组成的四面体中，一个面积最大的表面的面积为S1，三个面积较小的表面的面积之和为S2，若 ，则可认为四点共面。若有更多的点共面，输入保证其中任意四个点都满足上述不等式。
如有需要，可使用三角形面积的Heron公式，这个公式是数值稳定的：
其中a、b、c分别为三角形三边长，且 。
输入格式
输入第一行为一个整数，表示凸多面体的顶点数n，此后每行为三个浮点数，精度为小数点以后10位有效数字，表示一个顶点的直角坐标( x, y, z )，顶点可能按照任意的顺序给出。
输入顶点数目 ； , , 均小于10000。
输出格式
输出只有一行，为一个整数，表示同构象集元素的个数。
样例输入
输入每行为一个顶点的直角坐标( x, y, z )，精度为小数点以后10位有效数字：
4
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000
0.5000000000 0.8660254038 0.0000000000
0.5000000000 0.2886751346 20.0000000000
样例输出
6
样例解释
样例输入对应一个正三棱锥，前三个点是底面正三角形，位于z=0平面上，第四个点是正三棱锥的顶点，这个三棱锥的高是20，形状比较细长。根据前面所举的例子，一个正三棱锥的同构象集有六个元素，因此输出为6。
3. 黑白树
问题背景
在图论中，包含n个结点（结点编号为1~n）、n-1条边的无向连通图被称为树。在树中，任意一对结点间的简单路径总是惟一的。你拥有一棵白色的树——所有节点都是白色的。接下来，你需要处理c条指令：
1. 修改指令(0 v)：改变一个给定结点的颜色（白变黑，黑变白）；
2. 查询指令(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分。
否则，该组数据的得分取决于其中运行时间最长的数据的运行时间：运行时间越短，得分越高。
4. 度度熊与西瓜
问题背景
和其它熊不同，度度熊最喜欢吃的东西是西瓜，但是西瓜有一个很让它讨厌的地方——有很多的籽儿。可怜的度度熊并不知道这个世界上原来还有无籽西瓜这个东西。度度熊是一只很懒很懒的熊，并且它以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
