2 条题解

  • 0
    @ 2025-10-8 17:11:56

    题目大意是要求一条线段绕原点旋转一周得到的圆环面积与给定的矩形面积的交。我们可以利用微积分的思想,将整条线段看成无数个有宽度点,那么线段扫过的面积即为这些点扫过的面积之和。差分一下,就是最外层的点绕一圈形成的圆的面积减去最内层的点绕一圈形成的圆的面积。而最外层的点有一定在线段两端。最内层的点直接三分即可。于是圆环面积就搞定了。然后求面积交就是一大堆的特判。

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cmath>
    #define eps (1e-10)
    #define PI (acos(-1))
    using namespace std;
    inline int read(){
        int date=0,w=1;char c=0,last=0;
        while(c<'0'||c>'9'){last=c;c=getchar();}
        while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
        if(last=='-')w=-1;
        return date*w;
    }
    namespace __std{
        double h,w,x1,y1,x2,y2;
        inline double dis(double x,double y){return x*x+y*y;}
        double solve(double r){
            if(r*2<=h)return PI*r*r;
            else if(r*r>dis(h/2.0,w/2.0))return h*w;
            double t=sqrt(r*r-h*h/4.0)*h/4.0;
            if(2*r<w){
                double theta=PI/2.0-acos(h/r/2.0);
                return 4.0*(t+r*r*theta/2.0);
            }
            else{
                t+=sqrt(r*r-w*w/4.0)*w/4.0;
                double theta=PI/2.0-acos(h/r/2.0)-acos(w/r/2.0);
                return 4.0*(t+r*r*theta/2.0);
            }
        }
        void work(){
            double maxn,minn;
            if(dis(x1,y1)-dis(x2,y2)<eps)maxn=sqrt(dis(x2,y2));
            else maxn=sqrt(dis(x1,y1));
            while(fabs(x1-x2)>eps||fabs(y1-y2)>eps){
                double x3=(x2-x1)/3+x1,x4=(x2-x1)/3*2+x1;
                double y3=(y2-y1)/3+y1,y4=(y2-y1)/3*2+y1;
                if(dis(x3,y3)-dis(x4,y4)<eps){x2=x4;y2=y4;}
                else{x1=x3,y1=y3;}
            }
            minn=sqrt(dis(x1,y1));
            printf("%.10lf\n",solve(maxn)-solve(minn));
        }
        void init(){
            h=read();w=read();x1=read();y1=read();x2=read();y2=read();
            if(h>w)swap(h,w);
        }
    }
    int main(){
        int t=read();
        while(t--){
            __std::init();
            __std::work();
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:11:42
      /*
      题目大意是要求一条线段绕原点旋转一周得到的圆环面积与给定的矩形面积的交。
      我们可以利用微积分的思想,将整条线段看成无数个有宽度点,那么线段扫过的面积即为这些点扫过的面积之和。
      差分一下,就是最外层的点绕一圈形成的圆的面积减去最内层的点绕一圈形成的圆的面积。
      而最外层的点有一定在线段两端。
      最内层的点直接三分即可。
      于是圆环面积就搞定了。
      然后求面积交就是一大堆的特判
      */
      #include<iostream>
      #include<algorithm>
      #include<cstdio>
      #include<cmath>
      #define eps (1e-10)
      #define PI (acos(-1))
      using namespace std;
      inline int read(){
          int date=0,w=1;char c=0,last=0;
          while(c<'0'||c>'9'){last=c;c=getchar();}
          while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
          if(last=='-')w=-1;
          return date*w;
      }
      namespace __std{
          double h,w,x1,y1,x2,y2;
          inline double dis(double x,double y){return x*x+y*y;}
          double solve(double r){
              if(r*2<=h)return PI*r*r;
              else if(r*r>dis(h/2.0,w/2.0))return h*w;
              double t=sqrt(r*r-h*h/4.0)*h/4.0;
              if(2*r<w){
                  double theta=PI/2.0-acos(h/r/2.0);
                  return 4.0*(t+r*r*theta/2.0);
              }
              else{
                  t+=sqrt(r*r-w*w/4.0)*w/4.0;
                  double theta=PI/2.0-acos(h/r/2.0)-acos(w/r/2.0);
                  return 4.0*(t+r*r*theta/2.0);
              }
          }
          void work(){
              double maxn,minn;
              if(dis(x1,y1)-dis(x2,y2)<eps)maxn=sqrt(dis(x2,y2));
              else maxn=sqrt(dis(x1,y1));
              while(fabs(x1-x2)>eps||fabs(y1-y2)>eps){
                  double x3=(x2-x1)/3+x1,x4=(x2-x1)/3*2+x1;
                  double y3=(y2-y1)/3+y1,y4=(y2-y1)/3*2+y1;
                  if(dis(x3,y3)-dis(x4,y4)<eps){x2=x4;y2=y4;}
                  else{x1=x3,y1=y3;}
              }
              minn=sqrt(dis(x1,y1));
              printf("%.10lf\n",solve(maxn)-solve(minn));
          }
          void init(){
              h=read();w=read();x1=read();y1=read();x2=read();y2=read();
              if(h>w)swap(h,w);
          }
      }
      int main(){
          int t=read();
          while(t--){
              __std::init();
              __std::work();
          }
          return 0;
      }
      • 1

      【计算几何:圆与矩形面积交】圆环与矩形的面积交[Lydsy1706月赛]薄饼切割

      信息

      ID
      6589
      时间
      1000ms
      内存
      128MiB
      难度
      10
      标签
      递交数
      1
      已通过
      1
      上传者