半圆区域问题
平面直角坐标系中给定了若干个点，用一个给定圆心和半径的半圆最多能容纳多少个点?
Input：给定圆心坐标(x,y)及半径r，然后是坐标系中的点的个数N，接下来的N行就是这N个点的坐标。
Output：输出能容纳的最多的点数目即可。
解法：
1、按圆心及半径作圆；
2、设给定点集为N，对于给定点n∊N，作一条圆心与该点的连线，记为a。圆被连线a分成了两个半圆；
3、判断每一个m∊N属于哪一个半圆(可以同时属于两个半圆，如果m在a上)，得出当前情况下半圆能容纳的最多的点数；
4、遍历所有的n∊N，得出半圆容纳点数的最大值；
问题的关键在于第3步，给定一个点和一条直线，判断点在直线的上 方（左方）还是下方（右方）。
这道题目是重庆大学第三届程序设计比赛中的一个题目。当时信心满满、志在夺冠的我，就是栽在这个点上。在当时比赛的读秒情况下，解题的思路被限制了在通过各个点与圆心的连线和选定直径之间的夹角斜率去计算。但是实践证明，这种方法实在劳民伤财，调试起来太麻烦了，以致于比赛结束，我也没能将代码调试完成，夺冠梦碎……而在比赛结束后，再次想起这个题目的时候，立刻想到一个比计算斜率简单得多的解法。经此一役，我第一次注意到自己在读秒情况下的工作效率是如此之差，与平时形成鲜明对比……
后面想到的这个简便的方法是：将点的x坐标代入直线方程，得出y'值，与点的y坐标相比较即可。
穿越沙漠问题
吉普车来到x公里宽的沙漠边沿A点，吉普车的耗油量为1升/公里，总装油量为500升。 通常，吉普车必须用自身油箱中的油在沙漠中设置若干个临时储油点，才能穿越沙漠的。假设在沙漠边沿A点有充足的汽油可供使用，那么吉普车从A点穿过这片沙 漠到达终点B，至少要耗多少升油。请编写一个程序，计算最少的耗油量（精确到小数点后3位）。
（1） 假设吉普车在沙漠中行进时不发生故障；
（2） 吉普车在沙漠边沿A点到终点B的直线距离为x>=500公里(即沙漠宽度)；
Input：输入的第一行含一个正整数k (1<=k<=6)，表示测试例的个数。后面紧接着k行，每行对应一个测试例，包含一个正整数x，表示从A点到B点的距离（1<=x<=2000）。
Output：每个测试例对应一行输出，包含一个数，表示最少的油耗量。
这是为准备重庆大学第三届程序设计比赛而在网上收集到的一道题目。当时年级几大高手会诊，也没能治得了它。最终还是在我的手上得解，是以一直以来都被我津津乐道。
遇到这道题目，一开始总是想吉普车从A点出发的第一趟该走多远（当然出发时要载满油），然后回头（当然回头前要把尽可能多的油存在当地）。想来想去，似乎没个准。无论取什么值都跟“最省油通过沙漠”这个目标没有什么直接联系。
关键时候还是逆向思维让解题思路豁然开朗。一个满载的500升油能跑多少公里？当然是500公里（因为不需要回头了）；两个满载的500升油能跑多少公里？ 两个500升油，就需要吉普车加满第一个500升油出发、然后到达某一点把一些油储存起来、然后返回并刚好把油用完、然后加满第二个500升油再出发、跑到刚才放油的地点又刚好把油加满。这样一来，第一个500升油就经过了一次折返，跑了500/3公里，第二个500升油跑了500公里……如此类推，倒数第一个500升油能跑500/1公里、倒数第二个500升油能跑500/3公里、……、倒数第n个500升油能跑500/(2n-1)公里。这就是解题的 关键。
登山机器人问题
登山机器人是一个极富挑战性的高技术密集型科学研究项目。它涉及小车机械、飞行器控制、机器人学、机电一体化、单片机、数据融合、精密仪器、实时数字信号处理、图像处理与图像识别、知识工程与专家系统、决策、轨迹规划、自组织与自学习理论、多智能体协调、以及无线通讯等多项理论和技术，是一个典型的智能机器人系统。登山机器人为研究发展多智能体系统和多机器人之间的合作与对抗提供了 生动的研究模型。
登山机器人可以携带有限的能量。在登山过程中，登山机器人需要消耗一定能量，并且可以在机器人之间通过接触传递能量。用多个登山机器人接力登山可以极大地提高登山机器人的攀登高度。
给定n个登山机器人（1<n<100）。第i个登山机器人最多可以携带xi单位的能量，每攀高1米需要消耗能量yi单位。开始登山时n个登山机 器人均处于同一水平高度0，并且每个登山机器人初始时都携带了最多的能量。计算用这n个登山机器人进行不返回的接力登山可攀登的最高的高度。
Input：第1行中的整数为登山机器人个数n； 接下来的n行中每行一个整数，依次为x1,x2,…,xn； 最后的n行中每行一个实数，依次为y1,y2,…,yn。
Output：程序运行结束时，在屏幕上输出所找到的这n个登山机器人可攀登的最高的高度，精确到小数点后2位。
这道题目与穿越沙漠问题是一起得到的，但是很长时间都不能得解。在网络上进行相关搜索，仍然没有找到答案。网上出现较多的登山机器人问题是另一个版本，比这个版本简单许多。
还是分析分析这道题目吧。假设这样一个场景，机器人A攀高到x米时，停下来，等待机器人B攀高到x米处，然后将能量传递给B。A的能量耗尽，B继续攀高。一 开始A和B都同样攀高了x米，到x米的时候A将能量全部传递给B，此时B的能量刚好被加满。这就相当于A和B在攀高到x米的过程中使用的是A的油。为什么是使用A的油而不是B的油？理由是A比B性能差。所以先把性能差的机器人的油用掉，让性能好的继续攀高。
机器人的个数大于两个时也是同样的情况，所有机器人一起使用性能最差的机器人的油，油用完后这个机器人就停止攀高。其余机器人继续攀高，并又一起使用当前性能最差的机器人的油。按这样的贪心思想，最终能得出最优解。
分析到这里，似乎问题已经得解了。但是，性能谁高谁低如何区分？性能的高低有两个指标，载油要多、油耗要少。如果两个机器人，一个载油多但油耗少、一个则相反，那么很难判断到底是谁的性能高。
我曾经考虑过将给定的机器人两两比较，以得出性能排序。其办法是假设这两个机器人进行登山，计算先使用第一个的油和先使用第二个的油这两种情况下哪个的攀登高度更高，以判断哪个机器人的性能更高。但是两两比较出的性能放在多个机器人环境中并不适用，此法不可行。
那么，载油多和油耗少这两个指标能否通过什么公式换算成实际的性能指标呢？应该还是不行。所以，此题到这里，似乎没有什么好的方法可解了。
当然，有一种暴力的方法可解，就是穷举所有的可能性。第一个停下来的机器人有n种选择，第二个机器人有n-1种选择，……，那么一共有n!种情况需要穷举。O(n!)的复杂度是不可计算的，除非n非常小。
直到有一天，突然灵感来了……
要判断一堆机器人中哪个性能最差，计算它的载油量占总载油量的百分比、以及单位耗油量占总单位耗油量的百分比，这两项比值之比最低的机器人就是性能最差的！