1045.分段线性插值

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
using namespace std;

int main(int argc, char* argv[]) {
    map<int, int> mp;
    map<int, int>::iterator it;
    double x0, y0, x1, y1, ans;
    int n, x, y;
    char ch;

    mp[-1000000000] = 0;
    mp[1000000000] = 0;

    scanf("%d", &n);
    while (n--) {
        scanf(" %c", &ch);
        if (ch == 'A') {
            scanf("%d %d", &x, &y);
            mp[x] = y;
        } else {
            scanf("%d", &x);
            if (mp.find(x) != mp.end()) {
                ans = mp[x];
            } else {
                it = mp.upper_bound(x);
                x1 = it->first;
                y1 = it->second;
                it--;
                x0 = it->first;
                y0 = it->second;
                ans = y0 * (x - x1) / (x0 - x1) + y1 * (x - x0) / (x1 - x0);
            }
            printf("%.6f\n", ans);
        }
    }

    return 0;
}