cf139E

（ACM）浮点数精度 201707

http://codeforces.com/problemset/problem/139/E
两种处理浮点数下溢方法：
https://cn.vjudge.net/contest/170571#status/994495jj/H/0/

#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)a.size()
const int N=100070;
const double eps=1e-4;
int a[N],h[N],l[N],r[N],b[N/10],z[N/10];
struct Node {
    int p,x,ty;
    Node() {}
    Node(int a,int b,int c) {
        p=a;
        x=b;
        ty=c;
    }
    bool operator < (const Node &tmp) const {
        if(x!=tmp.x) return x<tmp.x;
        return ty<tmp.ty;
    }
}nn[N*5];
double mypow(double x,int y){
    double an=1;
    while(y){
        if(y&1){
            an*=x;
        }
        x*=x;
        y>>=1;
    }
    return an;
}
int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)) {
        ///read
        int cntn=0;
        rep(i,0,n) {
            scanf("%d%d%d%d",a+i,h+i,l+i,r+i);
            nn[++cntn]=Node(100-l[i],a[i]-h[i],0);
            nn[++cntn]=Node(100-l[i],a[i]-1,2);
            nn[++cntn]=Node(100-r[i],a[i]+1,0);
            nn[++cntn]=Node(100-r[i],a[i]+h[i],2);
        }
        rep(i,0,m) {
            scanf("%d%d",b+i,z+i);
            nn[++cntn]=Node(z[i],b[i],1);
        }
        ///solve
        sort(nn+1,nn+1+cntn);
//      for(int i=1;i<=cntn;++i) printf("%d %d %d\n",nn[i].x,nn[i].ty,nn[i].p);
        double ans=0,pre=0;
        int cnt0=0;
        rep(i,1,cntn+1) {
            int p=nn[i].p;
            int ty=nn[i].ty;
            if(ty==0) {
                if(p==0) {
                    ++cnt0;
                } else {
                    pre+=log(p)-log(100);
                }
            } else if(ty==1) {
                if(!cnt0) ans+=p*exp(pre);
            } else {
                if(p==0) {
                    --cnt0;
                } else {
                    pre-=log(p)-log(100);
                }
            }
        }
        printf("%.10f\n",ans);
    }
    return 0;
}

#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)a.size()
const int N=100070;
const double eps=1e-4;
int a[N],h[N],l[N],r[N],b[N/10],z[N/10],cnt[105];
struct Node {
    int p,x,ty;
    Node() {}
    Node(int a,int b,int c) {
        p=a;
        x=b;
        ty=c;
    }
    bool operator < (const Node &tmp) const {
        if(x!=tmp.x) return x<tmp.x;
        return ty<tmp.ty;
    }
}nn[N*5];
double mypow(double x,int y){
    double an=1;
    while(y){
        if(y&1){
            an*=x;
        }
        x*=x;
        y>>=1;
    }
    return an;
}
int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)) {
        ///read
        int cntn=0;
        rep(i,0,n) {
            scanf("%d%d%d%d",a+i,h+i,l+i,r+i);
            nn[++cntn]=Node(100-l[i],a[i]-h[i],0);
            nn[++cntn]=Node(100-l[i],a[i]-1,2);
            nn[++cntn]=Node(100-r[i],a[i]+1,0);
            nn[++cntn]=Node(100-r[i],a[i]+h[i],2);
        }
        rep(i,0,m) {
            scanf("%d%d",b+i,z+i);
            nn[++cntn]=Node(z[i],b[i],1);
        }
        ///solve
        sort(nn+1,nn+1+cntn);
//      for(int i=1;i<=cntn;++i) printf("%d %d %d\n",nn[i].x,nn[i].ty,nn[i].p);
        memset(cnt,0,sizeof(cnt));
        double ans=0;
        rep(i,1,cntn+1) {
            int p=nn[i].p;
            int ty=nn[i].ty;
            if(ty==0) {
                ++cnt[p];
            } else if(ty==1) {
                double res=1;
                rep(j,0,101) {
                    if(cnt[j]) {
                        res*=pow(j*0.01,cnt[j]);
                    }
                }
                ans+=res*p;
            } else {
                --cnt[p];
            }
        }
        printf("%.10f\n",ans);
    }
    return 0;
}