F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 1249. -- SGU277 HERO 动态凸包

1249: SGU277 HERO 动态凸包

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 650  Solved: 215
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

0 0 0 2 2 0
3
2 2
1 1
2 4

Sample Output

8
8
12

HINT

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

Source

[Submit][Status][Discuss]

HOME Back