2 条题解

  • 0
    @ 2025-10-8 17:05:47
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #define N 2003
    #define eps 1e-13
    using namespace std;
    int n,m,top,st,ed;
    bool mark[N];
    double xl[N],xr[N],ans;
    struct data{double x,y,r;}a[N],sk[N]; 
    struct line{double l,r;}p[N];
    int cmp(data a,data b){return a.r<b.r;}
    int cmp1(data a,data b){return a.x-a.r<b.x-b.r;}
    int cmp2(line a,line b){return a.l<b.l;}
    double pow(double x){return x*x;}
    double dis(data a,data b){return sqrt(pow(a.x-b.x)+pow(a.y-b.y));}
    double getf(double x)
    {
        double r,dis,len=0;
        int sz=0;
        for (int i=st;i<=ed;i++){
            if (xl[i]>=x||xr[i]<=x) continue;
            dis=sqrt(sk[i].r-pow(x-sk[i].x));
            p[++sz].l=sk[i].y-dis;  p[sz].r=sk[i].y+dis;
        }
        sort(p+1,p+sz+1,cmp2);
        int i,j;
        for (i=1;i<=sz;i++){
            r=p[i].r;
            for (j=i+1;j<=sz;j++){
                if (p[j].l>r) break;
                r=max(r,p[j].r);
            }
            len+=r-p[i].l; i=j;
        }
        return len;
    }
    double calc(double l,double fl,double fmid,double fr){return l/6.0*(fl+4.0*fmid+fr);}
    double simpson(double l,double mid,double r,double fl,double fmid,double fr,double s)
    {
        double m1=(l+mid)/2,m2=(mid+r)/2;
        double f1=getf(m1),f2=getf(m2);
        double g1=calc(mid-l,fl,f1,fmid),g2=calc(r-mid,fmid,f2,fr);
        if (fabs(g1+g2-s)<eps) return g1+g2;
        return simpson(l,m1,mid,fl,f1,fmid,g1)+simpson(mid,m2,r,fmid,f2,fr,g2);
    }
    void work()
    {
        for (int i=1;i<=m;i++) xl[i]=sk[i].x-sk[i].r,xr[i]=sk[i].x+sk[i].r,sk[i].r*=sk[i].r;
        int i,j; double l,r;
        double fl,fr,fmid;
        for (i=1;i<=m;i++){
            l=xl[i]; r=xr[i];
            for (j=i+1;j<=m;j++){
                if (xl[j]>r) break;
                r=max(r,xr[j]);
            }
            st=i; ed=j-1; i=j-1;
            double mid=(l+r)/2;
            fl=getf(l); fmid=getf(mid); fr=getf(r);
            //cout<<fl<<" "<<fr<<" "<<fmid<<endl;
            ans+=simpson(l,mid,r,fl,fmid,fr,calc(r-l,fl,fmid,fr));
        }
    }
    int main()
    {
        scanf("%d",&n);
        for (int i=1;i<=n;i++)scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
        sort(a+1,a+n+1,cmp);
        for (int i=1;i<=n-1;i++)
            for (int j=i+1;j<=n;j++)
                if (dis(a[i],a[j])<=a[j].r-a[i].r) {mark[i]=1;break;}
        for (int i=1;i<=n;i++)
         if (!mark[i]) sk[++m]=a[i];
        sort(sk+1,sk+m+1,cmp1);
        work();
        printf("%.3lf\n",ans);
    }
    
    • 0
      @ 2025-10-8 17:05:30
      #include<iostream>
      #include<cstdio>
      #include<cstring>
      #include<algorithm>
      #include<cmath>
      #define N 2003
      #define eps 1e-13
      using namespace std;
      int n,m,top,st,ed;
      bool mark[N];
      double xl[N],xr[N],ans;
      struct data{double x,y,r;}a[N],sk[N]; 
      struct line{double l,r;}p[N];
      int cmp(data a,data b){return a.r<b.r;}
      int cmp1(data a,data b){return a.x-a.r<b.x-b.r;}
      int cmp2(line a,line b){return a.l<b.l;}
      double pow(double x){return x*x;}
      double dis(data a,data b){return sqrt(pow(a.x-b.x)+pow(a.y-b.y));}
      double getf(double x)
      {
          double r,dis,len=0;
          int sz=0;
          for (int i=st;i<=ed;i++){
              if (xl[i]>=x||xr[i]<=x) continue;
              dis=sqrt(sk[i].r-pow(x-sk[i].x));
              p[++sz].l=sk[i].y-dis;  p[sz].r=sk[i].y+dis;
          }
          sort(p+1,p+sz+1,cmp2);
          int i,j;
          for (i=1;i<=sz;i++){
              r=p[i].r;
              for (j=i+1;j<=sz;j++){
                  if (p[j].l>r) break;
                  r=max(r,p[j].r);
              }
              len+=r-p[i].l; i=j-1;
          }
          return len;
      }
      double calc(double l,double fl,double fmid,double fr){return l/6.0*(fl+4.0*fmid+fr);}
      double simpson(double l,double mid,double r,double fl,double fmid,double fr,double s)
      {
          double m1=(l+mid)/2,m2=(mid+r)/2;
          double f1=getf(m1),f2=getf(m2);
          double g1=calc(mid-l,fl,f1,fmid),g2=calc(r-mid,fmid,f2,fr);
          if (fabs(g1+g2-s)<eps) return g1+g2;
          return simpson(l,m1,mid,fl,f1,fmid,g1)+simpson(mid,m2,r,fmid,f2,fr,g2);
      }
      void work()
      {
          for (int i=1;i<=m;i++) xl[i]=sk[i].x-sk[i].r,xr[i]=sk[i].x+sk[i].r,sk[i].r*=sk[i].r;
          int i,j; double l,r;
          double fl,fr,fmid;
          for (i=1;i<=m;i++){
              l=xl[i]; r=xr[i];
              for (j=i+1;j<=m;j++){
                  if (xl[j]>r) break;
                  r=max(r,xr[j]);
              }
              st=i; ed=j-1; i=j-1;
              double mid=(l+r)/2;
              fl=getf(l); fmid=getf(mid); fr=getf(r);
              //cout<<fl<<" "<<fr<<" "<<fmid<<endl;
              ans+=simpson(l,mid,r,fl,fmid,fr,calc(r-l,fl,fmid,fr));
          }
      }
      int main()
      {
          scanf("%d",&n);
          for (int i=1;i<=n;i++)scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].r);
          sort(a+1,a+n+1,cmp);
          for (int i=1;i<=n-1;i++)
              for (int j=i+1;j<=n;j++)
                  if (dis(a[i],a[j])<=a[j].r-a[i].r) {mark[i]=1;break;}
          for (int i=1;i<=n;i++)
           if (!mark[i]) sk[++m]=a[i];
          sort(sk+1,sk+m+1,cmp1);
          work();
          printf("%.3lf\n",ans);
      }
      
      • 1

      信息

      ID
      3843
      时间
      3000ms
      内存
      256MiB
      难度
      10
      标签
      递交数
      4
      已通过
      0
      上传者