● 1007忘了贴，呵呵 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: huhaiming (一生只爱她), 信区: Program
标  题: 1007忘了贴，呵呵
发信站: 荔园晨风BBS站 (Mon May 26 11:07:13 2003), 站内信件

//ZOJ Monthly, May 2003 Contest 1007
//Calculate the Integral
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int n,m,count[200],c[100],d[100];
double a[100],b[100],x[200];

int cmp(const void *p1,const void *p2){
        double t1=*(double *)p1,t2=*(double *)p2;
        if (t1>t2+1e-10) return 1;
        else if (t1<t2-1e-10) return -1;
        else return 0;
}

int bisearch(double y)
{
        int p=0,q=m-1,t;
        while(p<=q){
                t=(p+q)/2;
                if (y>x[t]+1e-10) p=t+1;
                else if (y<x[t]-1e-10) q=t-1;
                else return t;
        }
        return -1;
}

void compress()
{
        int i,j;
        qsort(x,m,sizeof(double),cmp);
        for(i=1,j=0;i<m;i++) if (fabs(x[i]-x[j])>1e-10) x[++j]=x[i];
        m=j+1;
        memset(count,0,sizeof(count));
        for(i=0;i<n;i++){
                c[i]=bisearch(a[i]);
                d[i]=bisearch(b[i]);
                for(j=c[i];j<d[i];j++) count[j]++;
        }
}

int main()
{
        int i;
        double t;
        freopen("1007.in","r",stdin);
        while(scanf("%d",&n)!=EOF){
                m=0;
                for(i=0;i<n;i++){
                        scanf("%lf%lf",&a[i],&b[i]);
                        x[m++]=a[i],x[m++]=b[i];
                }
                compress();
                t=0;
                for(i=0;i<m-1;i++) if (count[i]>0){
                        t+=(x[i+1]-x[i])*(pow(n,count[i])-1);
                }
                printf("%d\n%.10e\n",n,t);
        }
        return 0;
}

--

菩提本无树，明镜亦非台

本来无一物，何处惹尘埃

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店