题目描述
平面上有n个不重复的点。每次询问一个边平行坐标轴的矩形内（包含边界）的点组成的凸包的面积。、
输入格式
第一行两个整数k,n(1<=k<=1000000,3<=n<=3000)。
接下来n行，每行两个整数x_i,y_i(0<=x_i,y_i<=k)，表示点的坐标。
接下来一行一个整数m(1<=m<=1000000)，表示询问数量。
接下来m行，每行四个整数a,b,c,d(0<=a<b<=k,0<=c<d<=k)，表示询问的矩形范围为a<=x<=b,c<=y<=d。
输出格式
对于每个询问输出一行表示面积。保留小数点后一位。
-
题解
- 和这里的方向处理有点略微不同；
- 可以用排序扫描线+线段树维护出矩形边框四个方向可以卡住的切点，从南逆时针记为：$Ns,Ne,Nn,Nw$;
- $O(n^2)A$处理出一个点沿四个象限伸展且横纵坐标均单调的凸包，并处理出从沿凸包从$A$走到$B$的叉积和；
- 沿着$Ns,Ne,Nn,Nw$绕一圈查询对应象限的叉积和就$O(1)$求出面积；
- 由于一三，二四象限一定不会有交集所以可以分别存在一起；
- 注意由于要维护叉积求凸包的排序要有优先级；
- 算了说不清楚，。。。，还是去看Claris的题解吧。。。。。。TAT
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ls (k<<1)
#define rs (k<<1|1)
using namespace std;
const int N=,M=;
int n,m,q,Ne[M],Nw[M],Nn[M],Ns[M],top,T[N];
int mx[M<<];
ll A[N][N],B[N][N];
struct poi{
int x,y,z,w;
poi(int _x=,int _y=,int _z=,int _w=):x(_x),y(_y),z(_z),w(_w){};
poi operator -(const poi&a){return poi(x-a.x,y-a.y);}
}P[N],Q[M],que[N];
struct data{int a,b,c,d;}D[M];
il bool cmp1(const poi&a,const poi&b){return a.x==b.x?a.y<b.y:a.x<b.x;}
il bool cmp2(const poi&a,const poi&b){return a.y==b.y?a.x>b.x:a.y<b.y;}
il bool cmpx(const poi&a,const poi&b){return /*a.x==b.x?a.y<b.y:*/a.x<b.x;}
il bool cmpy(const poi&a,const poi&b){return /*a.y==b.y?a.x>b.x:*/a.y<b.y;}
il char gc(){
static char*p1,*p2,s[];
if(p1==p2)p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}
il int rd(){
int x=; char c=gc();
while(c<''||c>'')c=gc();
while(c>=''&&c<=''){x=x*+c-'';c=gc();}
return x;
}
ll crs(poi a,poi b){return (ll)a.x*b.y-(ll)a.y*b.x;}
il int Max(int a,int b){return T[a]<T[b]?b:a;}
il int query(int k,int l,int r,int x,int y){
if(l==x&&r==y)return mx[k];
else {
int mid=(l+r)>>;
if(y<=mid)return query(ls,l,mid,x,y);
else if(x>mid)return query(rs,mid+,r,x,y);
else return Max(query(ls,l,mid,x,mid),query(rs,mid+,r,mid+,y));
}
}
il void update(int k,int l,int r,int x,int v){
if(l==r)mx[k]=v;
else{
mx[k]=v;
int mid=(l+r)>>;
if(x<=mid)update(ls,l,mid,x,v);
else update(rs,mid+,r,x,v);
}
}
void build(int k,int l,int r){
mx[k]=;
if(l==r){T[l]=;return;}
int mid=(l+r)>>;
build(ls,l,mid);
build(rs,mid+,r);
}
int main(){
freopen("bzoj3839.in","r",stdin);
freopen("bzoj3839.out","w",stdout);
n=rd(); m=rd();
for(int i=;i<=m;++i)P[i].x=rd(),P[i].y=rd(),P[i].z=i; sort(P+,P+m+,cmp1);
for(int i=;i<=m;++i){
que[top=]=P[i];
for(int j=i-;j;--j)if(P[j].y<=P[i].y){
while(top>&&crs(que[top]-que[top-],P[j]-que[top])<=)top--;
que[++top]=P[j];
A[P[i].z][P[j].z]=A[P[i].z][que[top-].z]+crs(que[top-],P[j]);
}
que[top=]=P[i];
for(int j=i+;j<=m;++j)if(P[j].y>=P[i].y){
while(top>&&crs(que[top]-que[top-],P[j]-que[top])<=)top--;
que[++top]=P[j];
A[P[i].z][P[j].z]=A[P[i].z][que[top-].z]+crs(que[top-],P[j]);
}
}
sort(P+,P+m+,cmp2);
for(int i=;i<=m;++i){
que[top=]=P[i];
for(int j=i-;j;--j)if(P[j].x>=P[i].x){
while(top>&&crs(que[top]-que[top-],P[j]-que[top])<=)top--;
que[++top]=P[j];
B[P[i].z][P[j].z]=B[P[i].z][que[top-].z]+crs(que[top-],P[j]);
}
que[top=]=P[i];
for(int j=i+;j<=m;++j)if(P[j].x<=P[i].x){
while(top>&&crs(que[top]-que[top-],P[j]-que[top])<=)top--;
que[++top]=P[j];
B[P[i].z][P[j].z]=B[P[i].z][que[top-].z]+crs(que[top-],P[j]);
}
} q=rd();for(int i=;i<=q;++i)D[i].a=rd(),D[i].b=rd(),D[i].c=rd(),D[i].d=rd(); sort(P+,P+m+,cmpx);
for(int i=;i<=q;++i)Q[i]=(poi){D[i].a,D[i].c,D[i].d,i};
sort(Q+,Q+q+,cmpx);
build(,,n);
for(int i=q,j=m;i;--i){
while(j&&P[j].x>=Q[i].x)T[P[j].z]=m-j+,update(,,n,P[j].y,P[j].z),j--;
Nw[Q[i].w]=query(,,n,Q[i].y,Q[i].z);
} for(int i=;i<=q;++i)Q[i]=(poi){D[i].b,D[i].c,D[i].d,i};
sort(Q+,Q+q+,cmpx);
build(,,n);
for(int i=,j=;i<=q;++i){
while(j<=m&&P[j].x<=Q[i].x)T[P[j].z]=j,update(,,n,P[j].y,P[j].z),j++;
Ne[Q[i].w]=query(,,n,Q[i].y,Q[i].z);
} sort(P+,P+m+,cmpy);
for(int i=;i<=q;++i)Q[i]=(poi){D[i].c,D[i].a,D[i].b,i};
sort(Q+,Q+q+,cmpx);
build(,,n);
for(int i=q,j=m;i;--i){
while(j&&P[j].y>=Q[i].x)T[P[j].z]=m-j+,update(,,n,P[j].x,P[j].z),j--;
Ns[Q[i].w]=query(,,n,Q[i].y,Q[i].z);
} for(int i=;i<=q;++i)Q[i]=(poi){D[i].d,D[i].a,D[i].b,i};
sort(Q+,Q+q+,cmpx);
build(,,n);
for(int i=,j=;i<=q;++i){
while(j<=m&&P[j].y<=Q[i].x)T[P[j].z]=j,update(,,n,P[j].x,P[j].z),j++;
Nn[Q[i].w]=query(,,n,Q[i].y,Q[i].z);
}
for(int i=;i<=q;++i){
ll ans = A[Ns[i]][Ne[i]] + B[Ne[i]][Nn[i]] + A[Nn[i]][Nw[i]] + B[Nw[i]][Ns[i]];
// printf("%lld %lld %lld %lld\n",A[Nn[i]][Nw[i]],B[Ne[i]][Nn[i]],B[Nw[i]][Ns[i]],A[Ns[i]][Ne[i]]);
// printf("%d %d %d %d\n",Nn[i],Nw[i],Ns[i],Ne[i]);
printf("%.1lf\n",ans/2.0);
}
return ;
}
bzoj3839