解题思路:主要要考虑多个圆形覆盖时他的共同有效面积,并且考虑云朵投影面积是否在这个农场里面,其实题目容易理解,就是要运用数学思维去看,当只有一个圆形去覆盖农场时很简单,可以直接带进去,多个圆形时要多次循环输入就很复杂,我有思路但是不想去算了,希望大神考虑一下,还有就是微积分的方法,这个看的网上攻略,遇事不决,直接积分哈哈哈哈哈

注意事项:就是考虑多个圆形云朵覆盖的情况

参考代码:

#include <bits/stdc++.h>

using namespace std;

 

#define pdd pair<double,double>

#define l first

#define r second

 

const int N = 100;

double eps = 1e-6;

 

int n;

double a,b,x[N],y[N],r[N];

 

double f(double xi){

    priority_queue<pdd,vector<pdd>,greater<pdd> > pq;

    for(int i = 0;i < n;++i){

        double y1 =r[i]*r[i]-(x[i]-xi)*(x[i]-xi);

        if(y1 < eps)continue;

        y1 = sqrt(y1);

        pq.push(pdd(max(0.0,y[i]-y1),min(b,y[i]+y1)));

    }

    double ret = 0,last = 0;

    while(!pq.empty()){

        pdd seg = pq.top();pq.pop();

        if(seg.l > last)ret += seg.r - seg.l,last = seg.r;

        else if(seg.r > last)ret += seg.r - last,last = seg.r;

    }

    return ret;

}

 

double simpson(double l,double r){

    double mid = (l+r)/2;

    return (r-l)*(f(l)+4*f(mid)+f(r))/6;

}

 

double integral(double l,double r,double crt){

    double mid = (l+r)/2.0,L = simpson(l,mid),R = simpson(mid,r);

    if(fabs(crt-L-R)<eps)return L+R;

    return integral(l,mid,L) + integral(mid,r,R);

}

 

int main(){

    //freopen("in.txt","r",stdin);

    double ctg;

    cin >> a >> b >> ctg >> n;

    ctg = 1.0/tan(ctg/180.0*M_PI);

    for(int i = 0;i < n;++i){

        double z;cin >> x[i] >> y[i] >> z >> r[i];

        x[i] += z * ctg;

    }

    priority_queue<pdd,vector<pdd>,greater<pdd> > pq;

    for(int i = 0;i < n;++i){

        if(r[i]==0)continue;

        pq.push(pdd(max(0.0,x[i]-r[i]),min(a,x[i]+r[i])));

    }

    double last = 0,res = 0;

    while(!pq.empty()){

        pdd seg = pq.top();pq.pop();

        if(seg.l > last)res += integral(seg.l,seg.r,simpson(seg.l,seg.r)),last = seg.r;

        else if(seg.r > last)res += integral(last,seg.r,simpson(last,seg.r)),last = seg.r;

    }

    printf("%.2f\n",a*b-res);

    return 0;

}


 

0.0分

1 人评分

  评论区

  • «
  • »