2014
03-03

# Taunt Exposure Estimation

The brave knights of Camelot are constantly exposed to French taunting while assaulting the castle occupied by the French. Consequently, the taunting to which they are exposed varies with their distance from the castle during their assault, as well as variations in French taunting activity. We need to estimate the total amount of taunting that they are exposed to during a certain time period. Unfortunately, we only have access to a set of measurements at random times ― we do not have a continuous reading ― and, because of flaws in our archaic equipment, the measurements of taunting occur at unpredictable intervals.

The total amount of taunting will be given by the integral of the taunting intensity during the time period, as held in the observation data file. The amount of random noise, though, is fairly high, so that a simple trapezoid-rule integration is all that is merited.

• A single number, n, specifying the number of data points in the file
• n pairs of floating point numbers (given in increasing x order), separated by a comma ― in other words, a CSV file that could be input for a spreadsheet program [the first number is the x coordinate (time specification), the second is the y coordinate (the radiation reading)]
• 输出:

• A single number, n, specifying the number of data points in the file
• n pairs of floating point numbers (given in increasing x order), separated by a comma ― in other words, a CSV file that could be input for a spreadsheet program [the first number is the x coordinate (time specification), the second is the y coordinate (the radiation reading)]
• 样例输入:

9
0.0000, 0.5176
0.9869, 1.000
1.596, 1.114
2.370, 1.006
2.904, 0.8481
3.506, 0.5760
3.996, 0.4775
5.004, 0.3945
6.283, 1.004

样例输出:

0.00 to 6.28: 4.7288

#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <cctype>
#include <list>
#include <hash_map>
#include <stack>
#include <hash_set>
#include <hash_map>
#include <sstream>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <hash_map>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define mset(a) memset(a,0,sizeof(a))
#define mmset(a) memset(a,-1,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))
const int inf=1e9+7;
const long long linf=1e18;
typedef long double lf;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
typedef vector<int> vi;
pdd a[1111];
const double eps=1e-6;
int n;
int main(){
scanf("%d",&n);
for (int i=0;i<n;i++)
{
scanf("%lf,%lf",&a[i].X,&a[i].Y);
}
sort(a,a+n);
double ans=0;
for (int i=1;i<n;i++){
ans+=(a[i].X-a[i-1].X)/2*(a[i].Y+a[i-1].Y);
}
printf("%.2f to %.2f: %.4f\n",a[0].X,a[n-1].X,ans);
return 0;
}

1. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.