【NOIP2017提高A组模拟9.26】逗气

Description

Input

Output

Sample Input

3 2
1 8
4 5
7 9
3 1
5 2

Sample Output

6
5

Solution

首先把所有的点按照x放到数轴上，不论是询问还是其他的普通点（x就是a[]或c[]）
这样从左到右做，可以忽略绝对值
每次扫描到一个询问点就维护这个询问点的答案，这时只考虑到了x在这之前的
然后反着做一次就行了
怎么维护答案呢？
可以发现，每一个普通点都可以变成一条边，即对于每一个d的值，答案是多少
这样会有若干条线段，显然当线段重合时取最上面那条
这样可以用线段树做
也可以想成维护一个下凸壳，这个用单调队列就行了
然后二分，判断d[i]的值在哪条线段上，维护答案即可

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 200100
#define ll long long
using namespace std;
int n,m,d[N],tot=0,he=1,ta=0;
ll an[N];
struct node{
    ll x,y,z;
}a[N+N];
bool cnt(node x,node y){return x.x<y.x||(x.x==y.x&&x.z<y.z);}
double S(int j,int k)
{
    return (a[j].y-a[k].y)*1.0/(a[k].x-a[j].x);
}
double S1(int j,int k)
{
    return (a[j].y-a[k].y)*1.0/(a[j].x-a[k].x);
}
int main()
{
    freopen("gas.in","r",stdin);
    freopen("gas.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,1,n) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].z=0;
    fo(i,1,m) scanf("%lld%lld",&a[i+n].x,&a[i+n].y),a[i+n].z=i;
    n+=m;
    sort(a+1,a+n+1,cnt);
    fo(i,1,n)
    if(a[i].z==0)
    {
        while(ta>he&&S(d[ta],i)<S(d[ta-1],d[ta])) ta--;
        d[++ta]=i;
    }
    else
    {
        int l=he,r=ta;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(S(d[mid-1],d[mid])<a[i].y) l=mid;else r=mid;
        }
        int k;if(S(d[l],d[r])>a[i].y) k=d[l];else k=d[r];
        an[a[i].z]=max(an[a[i].z],a[k].y-abs(a[i].x-a[k].x)*a[i].y);
    }
    he=1;ta=0;
    fd(i,n,1)
    if(a[i].z==0)
    {
        while(ta>he&&S1(d[ta],i)<S1(d[ta-1],d[ta])) ta--;
        d[++ta]=i;
    }
    else
    {
        int l=he,r=ta;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(S1(d[mid-1],d[mid])<a[i].y) l=mid;else r=mid;
        }
        int k;if(S1(d[l],d[r])>a[i].y) k=d[l];else k=d[r];
        an[a[i].z]=max(an[a[i].z],a[k].y-abs(a[k].x-a[i].x)*a[i].y);
    }
    tot=0;
    fo(i,1,m) printf("%lld\n",an[i]);
}