Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

AC附代码

Posted by JiaJunpeng at 2011-07-17 21:58:25 on Problem 2177

Source Code

Problem: 2177  User: JiaJunpeng 
Memory: 192K  Time: 94MS 
Language: C++  Result: Accepted 

Source Code 
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stdio.h>
using namespace std;
double A,B,C,ru,val1,val2,delta,k1,b1,k2,b2;
struct sphere
{
    double x,y,z,r;
};
sphere a[111];
int n,ans,num,an[111],cnt[111];
int main()
{
    int i,j,s,p,q;
    double x1,y1,z1;
    while(scanf("%d",&n)==1)
    {
        for(i=0;i<n;i++)
           scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z,&a[i].r);
        ans=0;
        for(i=0;i<n;i++)
        {
           x1=a[i].x;
           y1=a[i].y;
           z1=a[i].z;
           num=0;
           memset(cnt,0,sizeof(cnt));
           for(j=0;j<n;j++)
           {
              A=x1*x1+y1*y1+z1*z1;
              B=-2*(x1*a[j].x+y1*a[j].y+z1*a[j].z);
              C=a[j].x*a[j].x+a[j].y*a[j].y+a[j].z*a[j].z-a[j].r*a[j].r;
              if(B*B-4*A*C>=0)
                 cnt[num++]=j;
           }
           if(num>ans)
           {
              ans=num;
              for(j=0;j<ans;j++)
                 an[j]=cnt[j];
           }
           for(j=i+1;j<n;j++)
           {
               val1=a[i].x*a[i].x+a[i].y*a[i].y+a[i].z*a[i].z-a[i].r*a[i].r;
               val2=a[j].x*a[j].x+a[j].y*a[j].y+a[j].z*a[j].z-a[j].r*a[j].r;
               ru=sqrt(val2/val1);
               if(a[j].x*a[i].y==a[i].x*a[j].y&&a[j].x*a[i].z==a[i].x*a[j].z)
                  continue;
               if(a[j].x*a[i].y==a[i].x*a[j].y)
               {
                   z1=(ru*a[j].x*val1-a[i].x*val2)/(ru*(a[j].x*a[i].z-a[i].x*a[j].z));
                   A=1+a[i].x*a[i].x/(a[i].y*a[i].y);
                   B=-2*a[i].x*(val1-z1*a[i].z)/(a[i].y*a[i].y);
                   C=(val1-z1*a[i].z)*(val1-z1*a[i].z)/(a[i].y*a[i].y)-val1+z1*z1;
                   delta=B*B-4*A*C;
                   if(delta<0)
                      continue;
                   x1=(-B+sqrt(delta))/(2*A);
                   y1=(val1-z1*a[i].z-x1*a[i].x)/a[i].y;
                   num=2;
                   cnt[0]=i;
                   cnt[1]=j;
                   for(int jj=0;jj<n;jj++)
                   {
                       if(jj==i||jj==j)
                          continue;
                       A=x1*x1+y1*y1+z1*z1;
                       B=-2*(x1*a[jj].x+y1*a[jj].y+z1*a[jj].z);
                       C=a[jj].x*a[jj].x+a[jj].y*a[jj].y+a[jj].z*a[jj].z-a[jj].r*a[jj].r;
                       if(B*B-4*A*C>=0)
                          cnt[num++]=jj;
                   }
                   if(ans<num)
                   {
                      ans=num;
                      for(int jj=0;jj<ans;jj++)
                         an[jj]=cnt[jj];
                   }
                   A=1+a[i].x*a[i].x/(a[i].y*a[i].y);
                   B=-2*a[i].x*(val1-z1*a[i].z)/(a[i].y*a[i].y);
                   C=(val1-z1*a[i].z)*(val1-z1*a[i].z)/(a[i].y*a[i].y)-val1+z1*z1;
                   delta=B*B-4*A*C;       
                   x1=(-B-sqrt(delta))/(2*A);
                   y1=(val1-z1*a[i].z-x1*a[i].x)/a[i].y;
                   num=2;
                   cnt[0]=i;
                   cnt[1]=j;
                   for(int jj=0;jj<n;jj++)
                   {
                       if(jj==i||jj==j)
                          continue;
                       A=x1*x1+y1*y1+z1*z1;
                       B=-2*(x1*a[jj].x+y1*a[jj].y+z1*a[jj].z);
                       C=a[jj].x*a[jj].x+a[jj].y*a[jj].y+a[jj].z*a[jj].z-a[jj].r*a[jj].r;
                       if(B*B-4*A*C>=0)
                          cnt[num++]=jj;
                   }
                   if(ans<num)
                   {
                      ans=num;
                      for(int jj=0;jj<ans;jj++)
                         an[jj]=cnt[jj];
                   }
               }
               else
               {
                   k1=-(a[j].x*a[i].z-a[i].x*a[j].z)/(a[j].x*a[i].y-a[i].x*a[j].y);
                   b1=(ru*a[j].x*val1-a[i].x*val2)/(ru*(a[j].x*a[i].y-a[i].x*a[j].y));
                   k2=-(k1*a[i].y+a[i].z)/a[i].x;
                   b2=(val1-b1*a[i].y)/a[i].x;
                   A=k1*k1+k2*k2+1;
                   B=2*k2*b2-k2*a[i].x+2*k1*b1-k1*a[i].y-a[i].z;
                   C=b2*b2-b2*a[i].x+b1*b1-b1*a[i].y;
                   delta=B*B-4*A*C;
                   if(delta<0) 
                     continue;
                   z1=(-B+sqrt(delta))/(2*A);
                   y1=k1*z1+b1;
                   x1=k2*z1+b2;
                   num=2;
                   cnt[0]=i;
                   cnt[1]=j;
                   for(int jj=0;jj<n;jj++)
                   {
                       if(jj==i||jj==j)
                          continue;
                       A=x1*x1+y1*y1+z1*z1;
                       B=-2*(x1*a[jj].x+y1*a[jj].y+z1*a[jj].z);
                       C=a[jj].x*a[jj].x+a[jj].y*a[jj].y+a[jj].z*a[jj].z-a[jj].r*a[jj].r;
                       if(B*B-4*A*C>=0)
                          cnt[num++]=jj;
                   }
                   if(ans<num)
                   {
                      ans=num;
                      for(int jj=0;jj<ans;jj++)
                         an[jj]=cnt[jj];
                   }
                   A=k1*k1+k2*k2+1;
                   B=2*k2*b2-k2*a[i].x+2*k1*b1-k1*a[i].y-a[i].z;
                   C=b2*b2-b2*a[i].x+b1*b1-b1*a[i].y;
                   delta=B*B-4*A*C; 
                   z1=(-B-sqrt(delta))/(2*A);
                   y1=k1*z1+b1;
                   x1=k2*z1+b2;
                   num=2;
                   cnt[0]=i;
                   cnt[1]=j;
                   for(int jj=0;jj<n;jj++)
                   {
                       if(jj==i||jj==j)
                          continue;
                       A=x1*x1+y1*y1+z1*z1;
                       B=-2*(x1*a[jj].x+y1*a[jj].y+z1*a[jj].z);
                       C=a[jj].x*a[jj].x+a[jj].y*a[jj].y+a[jj].z*a[jj].z-a[jj].r*a[jj].r;
                       if(B*B-4*A*C>=0)
                          cnt[num++]=jj;
                   }
                   if(ans<num)
                   {
                      ans=num;
                      for(int jj=0;jj<ans;jj++)
                        an[jj]=cnt[jj];
                   }    
               }
           }
        }
        printf("%d\n",ans);
        sort(an,an+ans);
        for(i=0;i<ans;i++)
          printf("%d ",an[i]+1);
        printf("\n");
    }
    return 0;
}

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> Source Code
> 
> Problem: 2177  User: JiaJunpeng 
> Memory: 192K  Time: 94MS 
> Language: C++  Result: Accepted 
> 
> Source Code 
> #include<iostream>
> #include<cstdlib>
> #include<cstring>
> #include<algorithm>
> #include<cmath>
> #include<stdio.h>
> using namespace std;
> double A,B,C,ru,val1,val2,delta,k1,b1,k2,b2;
> struct sphere
> {
>     double x,y,z,r;
> };
> sphere a[111];
> int n,ans,num,an[111],cnt[111];
> int main()
> {
>     int i,j,s,p,q;
>     double x1,y1,z1;
>     while(scanf("%d",&n)==1)
>     {
>         for(i=0;i<n;i++)
>            scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z,&a[i].r);
>         ans=0;
>         for(i=0;i<n;i++)
>         {
>            x1=a[i].x;
>            y1=a[i].y;
>            z1=a[i].z;
>            num=0;
>            memset(cnt,0,sizeof(cnt));
>            for(j=0;j<n;j++)
>            {
>               A=x1*x1+y1*y1+z1*z1;
>               B=-2*(x1*a[j].x+y1*a[j].y+z1*a[j].z);
>               C=a[j].x*a[j].x+a[j].y*a[j].y+a[j].z*a[j].z-a[j].r*a[j].r;
>               if(B*B-4*A*C>=0)
>                  cnt[num++]=j;
>            }
>            if(num>ans)
>            {
>               ans=num;
>               for(j=0;j<ans;j++)
>                  an[j]=cnt[j];
>            }
>            for(j=i+1;j<n;j++)
>            {
>                val1=a[i].x*a[i].x+a[i].y*a[i].y+a[i].z*a[i].z-a[i].r*a[i].r;
>                val2=a[j].x*a[j].x+a[j].y*a[j].y+a[j].z*a[j].z-a[j].r*a[j].r;
>                ru=sqrt(val2/val1);
>                if(a[j].x*a[i].y==a[i].x*a[j].y&&a[j].x*a[i].z==a[i].x*a[j].z)
>                   continue;
>                if(a[j].x*a[i].y==a[i].x*a[j].y)
>                {
>                    z1=(ru*a[j].x*val1-a[i].x*val2)/(ru*(a[j].x*a[i].z-a[i].x*a[j].z));
>                    A=1+a[i].x*a[i].x/(a[i].y*a[i].y);
>                    B=-2*a[i].x*(val1-z1*a[i].z)/(a[i].y*a[i].y);
>                    C=(val1-z1*a[i].z)*(val1-z1*a[i].z)/(a[i].y*a[i].y)-val1+z1*z1;
>                    delta=B*B-4*A*C;
>                    if(delta<0)
>                       continue;
>                    x1=(-B+sqrt(delta))/(2*A);
>                    y1=(val1-z1*a[i].z-x1*a[i].x)/a[i].y;
>                    num=2;
>                    cnt[0]=i;
>                    cnt[1]=j;
>                    for(int jj=0;jj<n;jj++)
>                    {
>                        if(jj==i||jj==j)
>                           continue;
>                        A=x1*x1+y1*y1+z1*z1;
>                        B=-2*(x1*a[jj].x+y1*a[jj].y+z1*a[jj].z);
>                        C=a[jj].x*a[jj].x+a[jj].y*a[jj].y+a[jj].z*a[jj].z-a[jj].r*a[jj].r;
>                        if(B*B-4*A*C>=0)
>                           cnt[num++]=jj;
>                    }
>                    if(ans<num)
>                    {
>                       ans=num;
>                       for(int jj=0;jj<ans;jj++)
>                          an[jj]=cnt[jj];
>                    }
>                    A=1+a[i].x*a[i].x/(a[i].y*a[i].y);
>                    B=-2*a[i].x*(val1-z1*a[i].z)/(a[i].y*a[i].y);
>                    C=(val1-z1*a[i].z)*(val1-z1*a[i].z)/(a[i].y*a[i].y)-val1+z1*z1;
>                    delta=B*B-4*A*C;       
>                    x1=(-B-sqrt(delta))/(2*A);
>                    y1=(val1-z1*a[i].z-x1*a[i].x)/a[i].y;
>                    num=2;
>                    cnt[0]=i;
>                    cnt[1]=j;
>                    for(int jj=0;jj<n;jj++)
>                    {
>                        if(jj==i||jj==j)
>                           continue;
>                        A=x1*x1+y1*y1+z1*z1;
>                        B=-2*(x1*a[jj].x+y1*a[jj].y+z1*a[jj].z);
>                        C=a[jj].x*a[jj].x+a[jj].y*a[jj].y+a[jj].z*a[jj].z-a[jj].r*a[jj].r;
>                        if(B*B-4*A*C>=0)
>                           cnt[num++]=jj;
>                    }
>                    if(ans<num)
>                    {
>                       ans=num;
>                       for(int jj=0;jj<ans;jj++)
>                          an[jj]=cnt[jj];
>                    }
>                }
>                else
>                {
>                    k1=-(a[j].x*a[i].z-a[i].x*a[j].z)/(a[j].x*a[i].y-a[i].x*a[j].y);
>                    b1=(ru*a[j].x*val1-a[i].x*val2)/(ru*(a[j].x*a[i].y-a[i].x*a[j].y));
>                    k2=-(k1*a[i].y+a[i].z)/a[i].x;
>                    b2=(val1-b1*a[i].y)/a[i].x;
>                    A=k1*k1+k2*k2+1;
>                    B=2*k2*b2-k2*a[i].x+2*k1*b1-k1*a[i].y-a[i].z;
>                    C=b2*b2-b2*a[i].x+b1*b1-b1*a[i].y;
>                    delta=B*B-4*A*C;
>                    if(delta<0) 
>                      continue;
>                    z1=(-B+sqrt(delta))/(2*A);
>                    y1=k1*z1+b1;
>                    x1=k2*z1+b2;
>                    num=2;
>                    cnt[0]=i;
>                    cnt[1]=j;
>                    for(int jj=0;jj<n;jj++)
>                    {
>                        if(jj==i||jj==j)
>                           continue;
>                        A=x1*x1+y1*y1+z1*z1;
>                        B=-2*(x1*a[jj].x+y1*a[jj].y+z1*a[jj].z);
>                        C=a[jj].x*a[jj].x+a[jj].y*a[jj].y+a[jj].z*a[jj].z-a[jj].r*a[jj].r;
>                        if(B*B-4*A*C>=0)
>                           cnt[num++]=jj;
>                    }
>                    if(ans<num)
>                    {
>                       ans=num;
>                       for(int jj=0;jj<ans;jj++)
>                          an[jj]=cnt[jj];
>                    }
>                    A=k1*k1+k2*k2+1;
>                    B=2*k2*b2-k2*a[i].x+2*k1*b1-k1*a[i].y-a[i].z;
>                    C=b2*b2-b2*a[i].x+b1*b1-b1*a[i].y;
>                    delta=B*B-4*A*C; 
>                    z1=(-B-sqrt(delta))/(2*A);
>                    y1=k1*z1+b1;
>                    x1=k2*z1+b2;
>                    num=2;
>                    cnt[0]=i;
>                    cnt[1]=j;
>                    for(int jj=0;jj<n;jj++)
>                    {
>                        if(jj==i||jj==j)
>                           continue;
>                        A=x1*x1+y1*y1+z1*z1;
>                        B=-2*(x1*a[jj].x+y1*a[jj].y+z1*a[jj].z);
>                        C=a[jj].x*a[jj].x+a[jj].y*a[jj].y+a[jj].z*a[jj].z-a[jj].r*a[jj].r;
>                        if(B*B-4*A*C>=0)
>                           cnt[num++]=jj;
>                    }
>                    if(ans<num)
>                    {
>                       ans=num;
>                       for(int jj=0;jj<ans;jj++)
>                         an[jj]=cnt[jj];
>                    }    
>                }
>            }
>         }
>         printf("%d\n",ans);
>         sort(an,an+ans);
>         for(i=0;i<ans;i++)
>           printf("%d ",an[i]+1);
>         printf("\n");
>     }
>     return 0;
> }
>

Home Page Go Back To top