赛题集锦—2008年百度之星程序设计大赛复赛题目

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，测试程序就会记录识别结果和询问次数并退出测试。

测试程序

我们准备了一个帮助你测试的客户端程序，点击下载Test.zip，需要的jre版本是1.6.0_05，下载jre。

注意

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.00000000000.00000000000.0000000000
1.00000000000.00000000000.0000000000
0.50000000000.86602540380.0000000000
0.50000000000.288675134620.0000000000
样例输出
6
样例解释
样例输入对应一个正三棱锥，前三个点是底面正三角形，位于z=0平面上，第四个点是正三棱锥的顶点，这个三棱锥的高是20，形状比较细长。根据前面所举的例子，一个正三棱锥的同构象集有六个元素，因此输出为6。

3.黑白树

问题背景
在图论中，包含n个结点（结点编号为1~n）、n-1条边的无向连通图被称为树。在树中，任意一对结点间的简单路径总是惟一的。你拥有一棵白色的树——所有节点都是白色的。接下来，你需要处理c条指令：
1. 修改指令(0v)：改变一个给定结点的颜色（白变黑，黑变白）；
2. 查询指令(1v)：询问从结点1到一个给定结点所经过的第一个黑色结点编号（假设沿着简单路径走）。
注意，在查询指令中，必须从结点1而不是结点v出发。如果结点1本身就是黑色，查询指令应该返回1。
输入说明
第一行包含两个正整数n,c，即结点数和指令条数。以下n-1行，每行两个正整数(ui,vi)(1<=ui 输出格式
对于每个查询操作(c=1的操作)，输出一行，包含一个整数，即第一个黑色结点的编号。如果不存在黑色结点，输出-1。
样例输入
98
12
13
24
29
59
79
89
68
13
08
16
17
02
19
02
19
样例输出
-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.度度熊与西瓜

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

有一天，这只懒熊突发奇想——如果能用一刀把那些籽儿全部切掉该多爽啊（当然，秉承懒的美德，切两刀是很辛苦的）。度度熊有一个很奇怪的仪器，可以检测出西瓜籽儿的坐标位置。于是度度熊立马动起手来（对于这种事，它一点都不懒）。但是它很快就发现，如果刻意追求切出的西瓜块儿不带籽儿，那它能吃到的西瓜就只有很少的一点了，这真是一件很扫兴的事。于是，它就只好作了个让步，只要切剩下的西瓜部分包含的籽儿的个数不大于给定的值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 接下来的n行表示n个籽儿的坐标。每行两个整数表示（极径，极角），籽儿保证在西瓜内，但可能在边界上。
输出格式
对每一组数据，输出单独一行，表示度度熊能切出来＂包含不大于m个籽儿的西瓜片＂的最大面积(四舍五入到小数点后5位)。
样例输入
2
10
1
090
2
145
745
10
0
090
2
145
745
样例输出
77.53982
39.26991