HS
AFO
HS的博客
LOJ6504「雅礼集训 2018 Day5」Convex

题目链接

LOJ

题目描述

公元 2038 年,在经历二战后,人类历史的科技进步水平突飞猛进,同此时刻,从电脑、网际网路以至人工智慧,高超的技术已大幅提升人类的生活水平与社会富裕。

与此同时,CyberLife 公司的革命性发明,仿生人,已经渐渐进入千家万户,它们代替人类进行工作,修路工人、居家保姆、老人看护、大楼保全、销售店员等工作均被仿生人所代替。

各种面向不同工作的仿生人有不同的型号,比如 Kara 的型号为 AX400,面向中低端收入人群的家庭管家。

一日,在 Kara 在做家务,它被命令洗干净一堆盘子,望着凸包形状的盘子,她突发奇想,如果只把凸包中的一部分点拎出来重新建成凸包,那么这个新凸包面积多大呢?

于是她对盘子建立平面直角坐标系,并把上的点根据她心情好坏按某种顺序标号,每次取出所有标号在一段区间中的点,并希望你帮她计算这些点构成的凸包的面积大小。

Kara 并不喜欢浮点数,所以输出的所有点的横纵坐标都为整数,同时你输出时要把答案乘以 $2$ 再四舍五入到整数位后再输出。

保证输入的所有点都在凸包上,没有三点共线,为了方便还保证坐标原点一定在凸包盘子内部。

输入格式

第一行两个正整数$n,m$表示凸包的点数与询问数。

下接$n$行,每行两个整数$x_i,y_i$描述凸包上的一个点。

下接$m$行,每行两个整数$l_i,r_i$描述一次询问,保证$r_i-l_i+1 \ge 3$。

输出格式

输出$m$行,每行一个整数表示面积乘以$2$再四舍五入后得到的数。

输入输出样例

输入 #1

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

输出 #1

29
15

说明/提示

对于全部数据,$n,m \le 150000,-10^9 \le x_i,y_i \le 10^9$。

分析

直接莫队的话,凸包插入是需要二分的,复杂度就是$O(n\sqrt{n}logn)$。
发现尽管插入不好做,但是删除是很简单的,维护链表,删除的时候只需要断掉就行了。
于是考虑回滚莫队,使得只有删除和撤销操作。
具体的,按左端点所在的块为第一关键字,右端点为第二关键字,其中右端点按递减排序。
对于每一块,初始将莫队的左端点移到块的左端点,右端点移到$n$,回答每次询问的时候移动左右端点,由于右端点是递减的,所以只需要将左端点移回即可。
只需要预处理出凸包的前驱后继就可以做了。
感觉其实不必保证右端点按递减排序也可以,只是复杂度会劣一些。

一些对我而言的坑

变量尽量避免重名。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 150010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
struct Node
{
    int x,y,id;
    double angle;
    void init(int o)
    {
        id=o;
        angle=atan2(y,x);
    }
    long long operator * (const Node &o)
    const{
        return 1ll*x*o.y-1ll*y*o.x;
    }
    bool operator < (const Node &o)
    const{
        return angle<o.angle;
    }
}p[maxn],tmp[maxn];
struct Query
{
    int l,r,id,bel;
    bool operator < (const Query &o)
    const{
        return bel==o.bel? r>o.r:bel<o.bel;
    }
}Q[maxn];
int n,m,B,pre[maxn],nxt[maxn];
long long cur=0,ans[maxn];
void del(int x)
{
    int l=pre[x],r=nxt[x];
    cur-=p[l]*p[x]+p[x]*p[r];
    cur+=p[l]*p[r];
    nxt[l]=r;
    pre[r]=l;
}
void undel(int x)
{
    int l=pre[x],r=nxt[x];
    cur-=p[l]*p[r];
    cur+=p[l]*p[x]+p[x]*p[r];
    nxt[l]=pre[r]=x;
}
int main()
{
    read(n,m);
    B=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        read(p[i].x,p[i].y);
        p[i].init(i);
        tmp[i]=p[i];
    }
    sort(tmp+1,tmp+1+n);
    for(int i=1;i<n;i++)
    {
        pre[tmp[i+1].id]=tmp[i].id;
        nxt[tmp[i].id]=tmp[i+1].id;
        cur+=tmp[i]*tmp[i+1];
    }
    pre[tmp[1].id]=tmp[n].id;
    nxt[tmp[n].id]=tmp[1].id;
    cur+=tmp[n]*tmp[1];
    for(int i=1;i<=m;i++)
    {
        read(Q[i].l,Q[i].r);
        Q[i].bel=(Q[i].l-1)/B;
        Q[i].id=i;
    }
    sort(Q+1,Q+1+m);
    int L=1,R=n;
    for(int i=1,j=1;i<=m;i=j)
    {
        int pos=Q[i].bel*B+1;
        while(R<n)
            undel(++R);
        while(L<pos)
            del(L++);
        while(j<=m&&Q[j].bel==Q[i].bel)
        {
            while(R>Q[j].r)
                del(R--);
            while(L<Q[j].l)
                del(L++);
            ans[Q[j].id]=cur;
            while(L>pos)
                undel(--L);
            j+=1;
        }
    }
    for(int i=1;i<=m;i++)
        printf("%lld\n",abs(ans[i]));
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

LOJ6504「雅礼集训 2018 Day5」Convex
计算几何+回滚莫队
扫描二维码继续阅读
2020-01-16