[NOI2005]月下柠檬树

C++14(g++5.4) 解法, 执行用时: 319ms, 内存消耗: 504K, 提交时间: 2019-08-20 21:48:17

#include<bits/stdc++.h>

#define FOR(x,y,z) for(int x=y,x##_=z;x<=x##_;++x)
#define DOR(x,y,z) for(int x=y,x##_=z;x>=x##_;--x)
#define FOR_(x,y,z,s) for(int x=y,x##_=z;x<=x##_;x+=s)
#define FOR__(x,y,z) for(int x=y,x##_=z;x<=x##_;x<<=1)
#define EOR(x,y) for(int x##_=head[x],y=edge[x##_].e;x##_;y=edge[x##_=edge[x##_].to].e)
#define EGOR(x,y,z) for(int x##_=head[x],y=edge[x##_].e,z=edge[x##_].c;x##_;y=edge[x##_=edge[x##_].to].e,z=edge[x##_].c)

#define clr(x,y) memset(x,y,sizeof(x))
#define szf(x) sizeof(x)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)

#define read2(x,y) read(x),read(y)
#define read3(x,y,z) read(x),read(y),read(z)
#define read4(x,y,z,w) read3(x,y,z),read(w)
#define reads(str) sf("%s",str)

#define ts (*this)
#define sf scanf
#define pf printf

#define ll long long
#define ull unsigned long long
#define db long double
#define ct clock_t
#define ck() clock()
#define rd rand()
#define rmx RAND_MAX
#define RD T*(rd*2-rmx)


using namespace std;

template<class T>bool tomin(T &x,T y){return x>y?x=y,1:0;}
template<class T>bool tomax(T &x,T y){return x<y?x=y,1:0;}
template<class T>void read(T &x){
    char c;
    x=0;
    int f=1;
    while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
    do x=(x<<3)+(x<<1)+(c^48);
    while(c=getchar(),c>='0'&&c<='9');
    x*=f;
}

const db Pi=acos(-1);
const int maxn=505;
int n;
db al;
struct node{
    db x,r;
}a[maxn];
namespace P10{
    void solve(){
        db r=a[1].r;
        if(a[1].x+a[1].r<a[2].x){
            db d=acos(r/(a[2].x-a[1].x));
            pf("%.2Lf",(Pi-d+tan(d))*r*r);
        }else pf("%.2Lf\n",Pi*r*r);
    }
}
namespace P100{
    const db EPS=1e-6;
    const db EPPS=1e-15;
    #define pw(x) ((x)*(x))
    bool ok[maxn];
    db K[maxn],B[maxn];
    db pl[maxn],pr[maxn];
    bool cmp(db x,db y){
        return y-x>=EPPS;
    }
    db F(db x){
        db val=0;
        FOR(i,1,n)if(cmp(a[i].x-a[i].r,x)&&cmp(x,a[i].x+a[i].r))
            tomax(val,sqrt(pw(a[i].r)-pw(a[i].x-x)));
        FOR(i,1,n-1)if(ok[i]&&cmp(pl[i],x)&&cmp(x,pr[i]))
            tomax(val,K[i]*x+B[i]);
        return val;
    }
    db Val(db a,db b){
        return (b-a)/6*(F(a)+F(b)+F((a+b)/2)*4);
    }
    db solve(db a,db b,db V){
        db mid=(a+b)/2;
        db Vl=Val(a,mid);
        db Vr=Val(mid,b);
        if(fabs(V-Vl-Vr)<EPS)return V;
        return solve(a,mid,Vl)+solve(mid,b,Vr);
    }
    db dis(db k,db b,db x){
        return fabs(x*k+b)/sqrt(1+k*k);
    }
    void solve(){
        FOR(i,1,n-1){
            if(cmp(a[i+1].x+a[i+1].r,a[i].x+a[i].r))continue;
            if(cmp(a[i+1].x-a[i+1].r,a[i].x-a[i].r))continue;
            ok[i]=1;
            db th=asin((a[i+1].r-a[i].r)/(a[i+1].x-a[i].x));
            K[i]=tan(th);
            B[i]=a[i].r*sqrt(K[i]*K[i]+1)-tan(th)*a[i].x;
            pl[i]=a[i].x-a[i].r*sin(th);
            pr[i]=a[i+1].x-a[i+1].r*sin(th);
        }
        db l=a[1].x-a[1].r;
        db r=a[n].x+a[n].r;
        FOR(i,1,n){
            tomin(l,a[i].x-a[i].r);
            tomax(r,a[i].x+a[i].r);
        }
        pf("%.2Lf",solve(l,r,Val(l,r))*2);
    }
}
int main(){
    srand(time(NULL));
    read(n);n++;
    sf("%Lf",&al);
    al=(db)1/tan(al);
    db H=0;
    FOR(i,1,n){
        sf("%Lf",&a[i].x);
        a[i].x=(H+=a[i].x)*al;
    }
    FOR(i,1,n-1)sf("%Lf",&a[i].r);
    if(n==2)P10::solve();
    else P100::solve();
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 155ms, 内存消耗: 504K, 提交时间: 2019-03-16 15:33:22

#include <cmath>
#include <cstdio>
#include <algorithm>
#define N 510
#define eps 1e-5
using namespace std;
struct circle
{
    double x , r;
}c[N];
struct line
{
    double x1 , y1 , x2 , y2;
}l[N];
double h[N];
int n , m;
inline double squ(double x)
{
    return x * x;
}
inline double f(double p)
{
    int i;
    double ans = 0;
    for(i = 1 ; i <= n ; i ++ )
        if(p >= c[i].x - c[i].r && p <= c[i].x + c[i].r)
            ans = max(ans , sqrt(squ(c[i].r) - squ(p - c[i].x)));
    for(i = 1 ; i <= m ; i ++ )
        if(p >= l[i].x1 && p <= l[i].x2)
            ans = max(ans , l[i].y1 + (p - l[i].x1) * (l[i].y2 - l[i].y1) / (l[i].x2 - l[i].x1));
    return ans;
}
inline double calc(double l , double r)
{
    return (r - l) * (f(l) + f(r) + f((l + r) / 2) * 4) / 6;
}
double simpson(double l , double r , double s)
{
    double mid = (l + r) / 2 , x = calc(l , mid) , y = calc(mid , r);
    if(fabs(x + y - s) <= eps) return s;
    return simpson(l , mid , x) + simpson(mid , r , y);
}
int main()
{
    int i;
    double alpha , t , L = 1e9 , R = -1e9;
    scanf("%d%lf" , &n , &alpha) , n ++ ;
    for(i = 1 ; i <= n ; i ++ ) scanf("%lf" , &h[i]) , h[i] += h[i - 1] , c[i].x = h[i] / tan(alpha);
    for(i = 1 ; i < n ; i ++ ) scanf("%lf" , &c[i].r);
    for(i = 1 ; i < n ; i ++ )
    {
        if(c[i + 1].x - c[i].x > fabs(c[i + 1].r - c[i].r))
        {
            m ++ ;
            t = c[i].r * (c[i].r - c[i + 1].r) / (c[i + 1].x - c[i].x) , l[m].x1 = c[i].x + t , l[m].y1 = sqrt(squ(c[i].r) - squ(t));
            t = c[i + 1].r * (c[i].r - c[i + 1].r) / (c[i + 1].x - c[i].x) , l[m].x2 = c[i + 1].x + t , l[m].y2 = sqrt(squ(c[i + 1].r) - squ(t));
        }
    }
    for(i = 1 ; i <= n + 1 ; i ++ ) L = min(L , c[i].x - c[i].r) , R = max(R , c[i].x + c[i].r);
    printf("%.2lf\n" , 2 * simpson(L , R , calc(L , R)));
    return 0;
}

详情