#6504. 「雅礼集训 2018 Day5」Convex

内存限制:512 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

样例输入 1

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

样例输出 1

29
15

数据范围与提示

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

  • 对于 10 \% 的数据满足 n, m \leq 2000
  • 对于 30 \% 的数据满足 n, m \leq 50000
  • 对于另 10 \% 的数据满足所有点的标号是按照极角序排序的,即点输入时按凸包逆时针顺序排序