Poj Solution 1819

http://poj.org/problem?id=1819

#include<iostream>
#include"math.h"
using namespace std;

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;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *