#P1249. SGU277 HERO 动态凸包

    ID: 259 传统题 1000ms 512MiB 尝试: 664 已通过: 110 难度: 7 上传者: 标签>CF2300提高+/省选-凸包有序集合叉积鞋带公式增量维护局部修复坐标变换

SGU277 HERO 动态凸包

题目描述

平面上最开始只包含3个点,然后还会依次出现 NN 个点。每新增一个点,请你求出包含这些点的周长最小的多边形的面积(也就是凸包的面积)。

输入格式

第一行为 66 个整数,表示最初的三个点的坐标(x1,y1),(x2,y2),(x3,y3)(x1,y1),(x2,y2),(x3,y3)。第二行仅一个数 NN。 以下N行,每行两个整数 (xi,yi)(xi,yi) ,表示新增的点的坐标。

输出格式

对于每次新增点的操作,请你输出新增完此点后当前的凸包的面积的两倍。

0 0 0 2 2 0
3
2 2
1 1
2 4
8
8
12

提示

N<=100000N<=100000 点的坐标巨大,目测在[−109,109][-10^9,10^9]

本站当前数据版本的坐标界限

初始3个点和所有新点的坐标均为整数,绝对值不超过 10910^9。此界限是对本站当前全部10组原测试逐文件扫描后的数据契约;原始存档“目测”说法不是正式证明。叉积、面积更新的中间乘积建议使用有符号128位整数,最终两倍凸包面积也用相同类型保存和输出。