Description
Consider N floating point numbers N representing the radii of N disks. We fix a disk in the xOy system, if we position it at a positive coordinate x (big enough), tangential to the 0x axis and above it and after that we push it to 0y until it becomes tangent to 0y or to the first disk that it meets on the way. In the configuration that results by fixing in order all the given disks, some of them can be considered as being dispensible, because, if we eliminate them, the total width of the configuration is the same, which means that there is no disk that can be moved to the left. Identify all the indispensible disks for a given configuration (in the configuration from above; the gray disks are dispensible).Input
The input has the following structure: the first line contains N ( N <= 1000), the number of disks; the next N lines contain N real numbers representing the radii of the disks, in the order they are fixed in the configuration.Output
The output will have the following structure: the first line will contain an integer K, representing the number of dispensable disks; each of the next K lines will contain the order number of the dispensable disks.Sample Input
7 4 0.1 0.5 3 0.5 4 1Sample Output
3 2 3 5 题目链接：http://poj.org/problem?id=1819
卡了我两天的一个题，难死了，要是把这个题放在比赛里我就死了，QAQ，题目的意思是说有N个圆放在坐标系中，依次摆放，和左边第一个可以相切的圆相切，注意，不一定是前一个，求，在不影响最右边的边界的时候，有哪些圆可以去掉。
我记得上来这个题没有一点思路，标神说先求圆心，提示了我这一点，一语惊醒梦中人啊，知道每个圆的半径了，可以通过勾股定理来求圆心，自己画一下图很明显就出来了，然后就判断每一个圆前面相切的那个圆是哪个，这个题就完成了，然后突然发现好简单，然后我就兴致冲冲的去敲这个题，然后，就卡死了，不是代码卡死了，是我不知道怎么求前面那一个相切的圆，想了一整天，越想越麻烦，无奈，去看了题解，原来这是最简单的一步！！！我想多了，真是，一看这个题的题解就懂了，根本不用思考，我靠，我脑子真是越来越笨了！！-_-|||
代码：
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #define eps 1e-9 #define inf 0x3f3f3f3f using namespace std; int main(){ double r[1010]; double x[1010];//圆心的横坐标 memset(x,0,sizeof(x)); double rr=0; int ri=0; int last[1010]; int n,i,j; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%lf",&r[i]); if(i==0){ x[i]=r[i]; last[i]=-1; } else{ x[i]=r[i]; last[i]=-1; for(j=0;j<i;j++){ double tmp=x[j]+sqrt((r[i]+r[j])*(r[i]+r[j])-(r[i]-r[j])*(r[i]-r[j]));//勾股定理 if(tmp-x[i]>eps){ x[i]=tmp; last[i]=j; } } } if(rr<x[i]+r[i]){//最右边的边界 rr=x[i]+r[i]; ri=i; } } int top=0; int sum[1010]; for(i=n-1;i>ri;i--){//最右边的边界不一定是最后一个圆，把后面的圆去掉 sum[top++]=i; } for(i=ri;i>=0;i=last[i]){//判断前面那一个相切的圆就这四行！！！加一个记录数组就行了，就这么简单 for(j=i-1;last[i]<j;j--){ sum[top++]=j; } } printf("%d\n",top); for(i=top-1;i>=0;i--){ printf("%d\n",sum[i]+1); } return 0; } 中级题就是中级题，比起初级难得不是一点啊
