Description

Input

Output

Sample Input

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

Sample Output

6
5

Data Constraint

Hint

第1 個聚逗陣的逗陣之靈是第1 個
第2 個聚逗陣的逗陣之靈是第3 個

Solution

• 先考慮選的聚集點都在當前聚逗陣左邊的情況，

• 對于第 i 個聚逗陣，且選第 j 個聚集點 比 選第 k 個聚集點，則有：bj?ci?di+aj?di>bk?ci?di+ak?di

• 整理可得：

  bj?bkaj?ak<?di

• 這便是斜率的形式，用單調隊列維護即可。

• 每次在隊列里二分查找斜率小于等于 ?di 的第一個就是答案了。

• 對于選的聚集點都在當前聚逗陣右邊的情況，倒過來處理即可，對于一左一右的情況已經被包含。

Code

#include<cstdio> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int N=2e5+1; struct data {LL x,y,z; }a[N],b[N],c[N]; int pos; int q[N]; LL ans[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline LL max(LL x,LL y) {return x>y?x:y; } inline bool cmp(data x,data y) {return x.x<y.x; } inline double pd(int x,int y) {return (b[x].y-b[y].y)*1.0/(b[x].x-b[y].x); } inline LL get1(data x) {int l=2,r=q[0],k=1;while(l<=r){int mid=(l+r)>>1;if(pd(q[mid],q[mid-1])>=-x.y) l=mid+1,k=mid; else r=mid-1;}return a[b[q[k]].z].y-abs(a[b[q[k]].z].x-x.x)*x.y; } inline LL get2(data x) {int l=2,r=q[0],k=1;while(l<=r){int mid=(l+r)>>1;if(pd(q[mid],q[mid-1])<=x.y) l=mid+1,k=mid; else r=mid-1;}return a[b[q[k]].z].y-abs(a[b[q[k]].z].x-x.x)*x.y; } int main() {int n=read(),m=read();for(int i=1;i<=n;i++) a[a[i].z=i].x=read(),a[i].y=read(),b[i]=a[i];for(int i=1;i<=m;i++) c[c[i].z=i].x=read(),c[i].y=read();sort(b+1,b+1+n,cmp);sort(c+1,c+1+m,cmp);for(int i=pos=1;i<=m;i++){while(pos<=n && c[i].x>=b[pos].x){while(q[0]>1 && pd(pos,q[q[0]-1])>=pd(q[q[0]],q[q[0]-1])) q[0]--;q[++q[0]]=pos++;}ans[c[i].z]=max(ans[c[i].z],get1(c[i]));}q[0]=0,pos=n;for(int i=m;i;i--){while(pos && c[i].x<=b[pos].x){while(q[0]>1 && pd(pos,q[q[0]-1])<=pd(q[q[0]],q[q[0]-1])) q[0]--;q[++q[0]]=pos--;}ans[c[i].z]=max(ans[c[i].z],get2(c[i]));}for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5390. 【NOIP2017提高A组模拟9.26】逗气的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。