1819.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:1819  User Id:fzk 
Memory:64K  Time:31MS
Language:C++  Result:Accepted

Source 

#include"iostream.h"
#include"math.h"

double r[1000];
double x[1000],t[1000];
char set[1000];
int n;

void init()
{int i;
cin>>n;
for(i=0;i<n;i++){set[i]=1;cin>>r[i];}
}

void doit()
{int i,j,k=0,s;

for(i=0;i<n;i++)
{x[i]=r[i];
k=-1;
for(j=0;j<i;j++)
	if(set[j])
	{t[j]=sqrt((r[i]+r[j])*(r[i]+r[j])-(r[i]-r[j])*(r[i]-r[j]))+x[j];
	if(t[j]>x[i]){x[i]=t[j];k=j;}
	}

for(j=k+1;j<i;j++)set[j]=0;

}
double right=0;
for(i=0;i<n;i++)if(x[i]+r[i]>right){right=x[i]+r[i];k=i;}
for(j=k+1;j<n;j++)set[j]=0;

for(i=0,s=0;i<n;i++)if(!set[i])s++;
cout<<s<<endl;
for(i=0;i<n;i++)if(!set[i])cout<<i+1<<endl;
}

int main()
{init();doit();
return 0;
}