lkMiles

退役oier

bzoj1502 月下柠檬树

之前计算几何老师来讲课的时候zcy推荐好题月下柠檬树后来zhx也推荐了,最近在写simpson就来做啦。

题解和题意就不写了网上好多都写的很好,主要是想说下自己写了这几天计算几何的感受。

本来觉得计算几何=大暴力,然而到了后面就觉得有些人的计算几何写得只有那么优美了,而我就经常会写好大一串来套板,显然非常不优,原因是没有发现图形的特殊性,就拿这道题来说,所有的圆心都在x轴上,所有的f(x)都是与y轴平行的,这意味着我们可以不用繁琐的去写直线和圆的交点,而直接通过勾股定理求解代码会非常短。而求圆的公切线,之前也是想到了很麻烦的做法,觉得可能会写50+行,结果去看了别人的标程maya惊呆了这明明就是三行的事情QAQ,很多对我而言要分类讨论的东西别人一个式子能表示完全,唔所以我还是太naive了,以后做题的时候要注意观察注意观察注意观察。

所以终于写完月下木宁木蒙木又寸了还是小小的开心一下>_<

http://paste.ubuntu.net/15204023/

唔还是粘一发代码吧

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define eps 1e-7
int sgn(double v){if(fabs(v)<eps) return 0;return v>0?1:-1;}
struct Point{
        double x,y;
        Point(double a=0,double b=0){ x=a,y=b;}
};
const int maxn=500+5;
struct Round{
        Point O;
        double r;
        void print(){printf("%.6f %.6f %.6f\n",O.x,O.y,r);}
} s[maxn];
struct Segment{
        Point st,ed;
        void print(){printf("%lf %lf  %lf %lf\n",st.x,st.y,ed.x,ed.y);}
}line[maxn*2];
int n;
int cnt;
double low,up;
void prepare(){
        double alpha;
        scanf("%d%lf",&n,&alpha);
        n++;
        double h=0;
        for(int i=1;i<=n;++i){
                scanf("%lf",&h);
                s[i].O.x=h/tan(alpha)+s[i-1].O.x;
                s[i].O.y=0;
        }
        for(int i=1;i<n;++i) scanf("%lf",&s[i].r);
        s[n].r=0;
        low=s[1].O.x-s[1].r,up=s[1].O.x+s[1].r;
        for(int i=2;i<=n;++i){
                low=min(low,s[i].O.x-s[i].r);
                up=max(up,s[i].O.x+s[i].r);
        }
        for(int i=1;i<n;++i){
                double d=s[i+1].O.x-s[i].O.x;
                if(sgn(fabs(d)-fabs(s[i].r-s[i+1].r))<=0) continue;//一个被另一个完全包含不必要求公切线
                double sint=(s[i].r-s[i+1].r)/d;
                double cost=sqrt(1-sint*sint);
                line[++cnt].st=Point(s[i].O.x+sint*s[i].r,s[i].O.y+cost*s[i].r);
                line[cnt].ed=Point(s[i+1].O.x+sint*s[i+1].r,s[i+1].O.y+cost*s[i+1].r);
                cnt++;
                line[cnt].st=line[cnt-1].st,line[cnt].st.y*=-1;
                line[cnt].ed=line[cnt-1].ed,line[cnt].ed.y*=-1;
        }
    //    for(int i=1;i<=cnt;++i) line[i].print();
}
double pos[10*maxn];
double f(double x){
        int len=0;
        for(int i=1;i<=n;++i){
                if(sgn(fabs(x-s[i].O.x)-s[i].r)>=0) continue;
                double d=fabs(x-s[i].O.x);
                pos[++len]=sqrt(s[i].r*s[i].r-d*d);
                pos[++len]=-sqrt(s[i].r*s[i].r-d*d);
        }
        for(int i=1;i<=cnt;++i){
                Point l,r;
                if(line[i].st.x<line[i].ed.x) l=line[i].st,r=line[i].ed;
                else l=line[i].ed,r=line[i].st;
                if(sgn(x-l.x)>=0&&sgn(x-r.x)<=0){
                        double tant=(r.y-l.y)/(r.x-l.x);
                        double le=x-l.x;
                        pos[++len]=le*tant+l.y;
                }
        }
        if(len<=1) return 0;
        sort(pos+1,pos+len+1);
    //    cout<<x<<" "<<pos[len]-pos[1]<<endl;
        return pos[len]-pos[1];
}
double simpson(double l,double r){
        double mid=l+(r-l)/2;
        return (f(l)+4*f(mid)+f(r))*(r-l)/6;
}
double area(double l,double r,double val,double EPS){
        double mid=l+(r-l)/2;
        double L=simpson(l,mid);
        double R=simpson(mid,r);
        if(fabs(L+R-val)<=eps) return L+R;
        else return area(l,mid,L,EPS/2)+area(mid,r,R,EPS/2);
}
int main(){
        freopen("1502.in","r",stdin);
        freopen("1502.out","w",stdout);
        prepare();
        printf("%.2f\n",area(low,up,simpson(low,up),eps));
        return 0;
}

评论
热度(2)
©lkMiles
Powered by LOFTER