3200.cpp

北大ACM题库3200题代码（巴别塔问题） 算法分析期末实验

#include<math.h>
#include<string.h>
#include <stdio.h>


double x[1000],y[1000],r[1000];

int k;
int n;

double centre[1000][2];
double weight[1000];

void weig(int i)                   //重量计算
{
    weight[i]=r[i]*r[i]*acos(-1);

    for(int j=i-1;j>=0;j--)
    {
        weight[j]=weight[j+1]+r[j]*r[j]*acos(-1);
        weight[j]=weight[j+1]+r[j]*r[j]*acos(-1);
    }
}

void cent(int i)                 //重心计算
{
    centre[i][0]=x[i];
    centre[i][1]=y[i];
    for(int j=i-1;j>=0;j--)
    {
        centre[j][0]=(centre[j+1][0]*weight[j+1]+r[j]*r[j]*acos(-1)*x[j])/(weight[j+1]+r[j]*r[j]*acos(-1));
        centre[j][1]=(centre[j+1][1]*weight[j+1]+r[j]*r[j]*acos(-1)*y[j])/(weight[j+1]+r[j]*r[j]*acos(-1));
    }
}

double distance(double x1,double y1,double x2,double y2)  //重心距离
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

bool func(int i)            //判断
{
    for(int j=1;j<=i;j++)
    {
        if(distance(centre[j][0],centre[j][1],x[j-1],y[j-1])>=r[j-1])
        {
            return 0;
        }
    }
    return 1;
}


int main()  //主函数
{

    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;
        k=n;
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        memset(r,0,sizeof(r));
        memset(weight,0,sizeof(weight));
        memset(centre,0,sizeof(centre));   //归零
        int i;
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
            if(k==n)
            {
                weig(i);    
                cent(i);
                if(!func(i))
                {
                    k=i;
                }
            }
        }

        if(k>=n)
            printf("Feasible\n");
        else
            printf("Unfeasible %d\n",k);
    }
    return 0;
}