[CSP-S模拟测试]:A（单调栈维护凸包+二分答案）

输入格式

　　第一行两个整数$N,Q$。
　　接下来的$N$行，每行两个整数$a_i,b_i$。
　　接下来的$Q$行，每行一个整数$x$。

输出格式

　　对于每个询问，输出一行一个整数表示答案。

样例

样例输入：

2 4
3 0
4 -2
-1
0
1
2

样例输出：

6
0
3
12

数据范围与提示

　　每个测试点$10$分，共$10$个测试点：

对于所有的数据，有：$1\leqslant N,Q,|a_i|,|b_i|,|x|<32323$。

题解

发现式子中没有$c_i$，所以可以把一个$x$提出来，于是就变成了一个一次函数，而对于$x$的正负分类讨论就好了。

对于一次函数，可以用单调栈维护凸包找位于凸包上的$a_i,b_i$，然后对于每一组询问二分答案即可。

时间复杂度：$\Theta((N+Q)\log N)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include
using namespace std;
struct rec{int a,b;}e[500001],S[500001],L[500001],R[500001];
int N,Q;
int top,l,r;
bool cmp1(rec a,rec b){return a.a==b.a?a.bb.b:a.a1&&ask(S[top-1],S[top])>ask(S[top],e[i]))top--;
		S[++top]=e[i];
	}
	for(int i=1;i<=top;i++)L[++l]=S[i];
	sort(e+1,e+N+1,cmp2);top=0;
	for(int i=1;i<=N;i++)
	{
		while(top&&(S[top].a==e[i].a||ask(S[top],e[i])>0))top--;
		while(top>1&&ask(S[top-1],S[top])0)
		{
			int lft=1,rht=l,res=1;
			while(lft<=rht)
			{
				int mid=(lft+rht)>>1;
				if(ask(L[mid-1],L[mid])>1;
				if(ask(R[mid-1],R[mid])

rp++