记录编号	420641	评测结果	AAAA
题目名称	[NOIP 1999]旅行家的预算	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2017-07-05 10:32:25	内存使用	0.31 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

struct DATA{ 
    double D, P;

    DATA(){ ;}

    bool operator < (const DATA &a) const { 
        return D < a.D;
    }
};

double D1, C, D2;
double longest, ans;
DATA data[15];
int N;

int main(){ 
#ifndef LOCAL
    freopen("lyuxing.in", "r", stdin);
    freopen("lyuxing.out", "w", stdout);
#endif
    scanf("%lf%lf%lf%lf%d", &D1, &C, &D2, &(data->P), &N);

    data->D = 0; longest = C * D2;
    for(int i = 1; i <= N; ++i) scanf("%lf%lf", &((data + i)->D), &((data + i)->P));
    data[N + 1].D = D1, data[N + 1].P = 0;

    sort(data + 1, data + 1 + N);
    //for(int i = 0; i <= N; ++i) printf("%lf %lf\n", (data + i)->D, (data + i)->P);

    int i = 0;
    double now_C = 0;
    bool flag;
    while(i <= N){ 
        if(data[i + 1].D - data[i].D > longest){ 
            printf("No Solution");
            return 0;
        }
        flag = false;

        for(int j = i + 1; j <= N + 1 && data[j].D - data[i].D <= longest; ++j){ 
            if(data[j].P < data[i].P){ 
                if(now_C * D2 >= data[j].D - data[i].D){ 
                    now_C -= (data[j].D - data[i].D) / D2;
                    i = j;
                    flag = true;
                    break ;
                }
                else { 
                    ans += ((data[j].D - data[i].D) / D2 - now_C) * data[i].P;
                    now_C = 0;
                    i = j;
                    flag = true;
                    break;
                }
            }
        }

        if(!flag){ 
            int n = i + 1;
            for(int j = i + 1; j <= N + 1 && data[j].D - data[i].D <= longest; ++j){ 
                if(data[j].P < data[n].P) n = j;
            }

            ans += (C - now_C) * data[i].P;
            now_C = C - (data[n].D - data[i].D) / D2;
            i = n;
        }
    }
    printf("%.2lf", ans);
    return 0;
}