【PA2013】【BZOJ3839】Działka
Description
平面にはn個の重複しない点がある.1つのエッジ平行座標軸の矩形内(境界を含む)の点からなるバンプの面積を尋ねるたびに.Input
1行目の2つの整数k,n(1<=k<=100000,3<=n<=3000).次のn行、行ごとに2つの整数x_i,y_i(0<=x_i,y_i<=k)は、点の座標を表す.次の行は整数m(1<=m<=1000000)で、問い合わせ数を表します.次に、m行は、行毎に4つの整数a,b,c,d(0<=a各問合せ出力に対して1行が面積を表す.小数点以下の1桁を保持します.Sample Input
9 7
1 1
1 3
3 3
3 1
6 5
6 6
7 3
3
0 4 0 4
2 7 0 7
3 7 3 6 Sample Output
4.0
10.0
6.0 HINT
Source
150 s时限,卡评测好题考虑把要求的凸包分成四部分:左上,左下,右上,右下それぞれ各点対この四つの方向に凸包を构筑する面积(叉积)を求め、各问い合わせに線分树+走査线で叉积を积み重ねて和を求め、それから二つを割ると答え问い合わせが限られているその四つの范囲が直接処理できないので、问い合わせ+反発を解くのはすごい…%Claris...
平面にはn個の重複しない点がある.1つのエッジ平行座標軸の矩形内(境界を含む)の点からなるバンプの面積を尋ねるたびに.Input
1行目の2つの整数k,n(1<=k<=100000,3<=n<=3000).次のn行、行ごとに2つの整数x_i,y_i(0<=x_i,y_i<=k)は、点の座標を表す.次の行は整数m(1<=m<=1000000)で、問い合わせ数を表します.次に、m行は、行毎に4つの整数a,b,c,d(0<=a
9 7
1 1
1 3
3 3
3 1
6 5
6 6
7 3
3
0 4 0 4
2 7 0 7
3 7 3 6 Sample Output
4.0
10.0
6.0 HINT
Source
150 s时限,卡评测好题考虑把要求的凸包分成四部分:左上,左下,右上,右下それぞれ各点対この四つの方向に凸包を构筑する面积(叉积)を求め、各问い合わせに線分树+走査线で叉积を积み重ねて和を求め、それから二つを割ると答え问い合わせが限られているその四つの范囲が直接処理できないので、问い合わせ+反発を解くのはすごい…%Claris...
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 3010
#define GET (ch>='0'&&ch<='9')
#define lchild rt<<1,l,mid
#define rchild rt<<1|1,mid+1,r
#define ln rt<<1
#define rn rt<<1|1
#define SIZE 1000010
#define LL long long
using namespace std;
int k,n,m;
LL ans;
int sta[MAXN],top;
inline void in(int &x)
{
char ch=getchar();x=0;
while (!GET) ch=getchar();
while (GET) x=x*10+ch-'0',ch=getchar();
}
LL f[5][MAXN][MAXN];
int que[5][SIZE];
struct Point
{
int x,y,id;
inline friend Point operator -(Point a,Point b) {return (Point){a.x-b.x,a.y-b.y};}
inline friend LL operator *(Point a,Point b) {return (LL)a.x*b.y-(LL)a.y*b.x;}
}s[MAXN];
inline LL cross(Point a,Point b,Point c) {Point A=b-a,B=c-b;return B*A;}
inline bool cmp1(Point a,Point b) {return a.x==b.x?a.y<b.y:a.x<b.x;}
inline bool cmp2(Point a,Point b) {return a.x==b.x?a.y>b.y:a.x<b.x;}
inline bool cmp3(Point a,Point b) {return a.x<b.x;}
inline bool cmp4(Point a,Point b) {return a.y<b.y;}
int vis[MAXN],pos;
struct seg {int l,r,x;}tree[SIZE<<2];
inline void build(int rt=1,int l=0,int r=k)
{
tree[rt].x=0;tree[rt].l=l;tree[rt].r=r;int mid=(l+r)>>1;
if (l==r) return; build(lchild);build(rchild);
}
inline void modify(int rt,int x,int delta)
{
int L=tree[rt].l,R=tree[rt].r,mid=(L+R)>>1; tree[rt].x=delta;
if (L==R) return;
if (x<=mid) modify(ln,x,delta); else modify(rn,x,delta);
}
inline int merge(int x,int y) {return vis[x]>vis[y]?x:y;}
inline int query(int rt,int l,int r)
{
int L=tree[rt].l,R=tree[rt].r,mid=(L+R)>>1;
if (l<=L&&r>=R) return tree[rt].x;
if (r<=mid) return query(ln,l,r);
if (l>mid) return query(rn,l,r);
return merge(query(ln,l,mid),query(rn,mid+1,r));
}
struct Query
{
int a,b,c,d;
inline bool operator <(const Query& x)const {return a<x.a;}
}q[SIZE],newq[SIZE];
int main()
{
in(k);in(n);
for (int i=1;i<=n;i++) in(s[i].x),in(s[i].y),s[i].id=i;
sort(s+1,s+n+1,cmp1);
for (int i=2;i<=n;i++)//A
{
top=0;sta[top]=i;int l=s[sta[top]].id;
for (int j=i-1;j;j--)
if (s[j].y<=s[i].y)
{
while (top&&cross(s[j],s[sta[top]],s[sta[top-1]])<0) top--;
f[1][l][s[j].id]=f[1][l][s[sta[top]].id]+s[sta[top]]*s[j];sta[++top]=j;
}
}
sort(s+1,s+n+1,cmp2);
for (int i=1;i<n;i++)//B
{
top=0;sta[top]=i;int l=s[sta[top]].id;
for (int j=i+1;j<=n;j++)
if (s[j].y<=s[i].y)
{
while (top&&cross(s[sta[top-1]],s[sta[top]],s[j])<0) top--;
f[2][l][s[j].id]=f[2][l][s[sta[top]].id]+s[sta[top]]*s[j];sta[++top]=j;
}
}
for (int i=2;i<=n;i++)//C
{
top=0;sta[top]=i;int l=s[sta[top]].id;
for (int j=i-1;j;j--)
if (s[j].y>=s[i].y)
{
while (top&&cross(s[j],s[sta[top]],s[sta[top-1]])>0) top--;
f[3][l][s[j].id]=f[3][l][s[sta[top]].id]+s[sta[top]]*s[j];sta[++top]=j;
}
}
sort(s+1,s+n+1,cmp1);
for (int i=1;i<n;i++)//D
{
top=0;sta[top]=i;int l=s[sta[top]].id;
for (int j=i+1;j<=n;j++)
if (s[j].y>=s[i].y)
{
while (top&&cross(s[sta[top-1]],s[sta[top]],s[j])>0) top--;
f[4][l][s[j].id]=f[4][l][s[sta[top]].id]+s[sta[top]]*s[j];sta[++top]=j;
}
}
in(m);
for (int i=1;i<=m;i++) in(q[i].a),in(q[i].b),in(q[i].c),in(q[i].d);
for (int i=1;i<=m;i++) newq[i]=(Query){q[i].d,q[i].a,q[i].b,i};//
sort(s+1,s+n+1,cmp4);sort(newq+1,newq+m+1);int i,j;
for (build(1,0,k),i=j=1;i<=m;i++)
{
while (j<=n&&s[j].y<=newq[i].a) modify(1,s[j].x,s[j].id),vis[s[j++].id]=++pos;
que[1][newq[i].d]=query(1,newq[i].b,newq[i].c);
}
for (int i=1;i<=m;i++) newq[i]=(Query){q[i].c,q[i].a,q[i].b,i};
sort(s+1,s+n+1,cmp4);sort(newq+1,newq+m+1);
for (build(1,0,k),i=m,j=n;i;i--)
{
while (j&&s[j].y>=newq[i].a) modify(1,s[j].x,s[j].id),vis[s[j--].id]=++pos;
que[3][newq[i].d]=query(1,newq[i].b,newq[i].c);
}
for (int i=1;i<=m;i++) newq[i]=(Query){q[i].b,q[i].c,q[i].d,i};
sort(s+1,s+n+1,cmp3);sort(newq+1,newq+m+1);
for (build(1,0,k),i=j=1;i<=m;i++)
{
while (j<=n&&s[j].x<=newq[i].a) modify(1,s[j].y,s[j].id),vis[s[j++].id]=++pos;
que[4][newq[i].d]=query(1,newq[i].b,newq[i].c);
}
for (int i=1;i<=m;i++) newq[i]=(Query){q[i].a,q[i].c,q[i].d,i};
sort(s+1,s+n+1,cmp3);sort(newq+1,newq+m+1);
for (build(1,0,k),i=m,j=n;i;i--)
{
while (j&&s[j].x>=newq[i].a) modify(1,s[j].y,s[j].id),vis[s[j--].id]=++pos;
que[2][newq[i].d]=query(1,newq[i].b,newq[i].c);
}
for (int i=1;i<=m;i++)
{
ans=f[1][que[1][i]][que[2][i]]-f[2][que[1][i]][que[4][i]]-f[3][que[3][i]][que[2][i]]+f[4][que[3][i]][que[4][i]];
printf("%lld.%d
",ans>>1,ans&1ll?5:0);
}
}