logo AlgoBeat OnlineJudge
登录 注册

#214879. [CCPC 2024 哈尔滨站] 凹包

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

简单多边形是平面中由线段组成的闭合曲线,这些线段首尾相连,除了因连接共用的线段端点,任何两个线段都不能彼此相交。

简单多边形可以分为两类:凸多边形和凹多边形。一个凸多边形是指:多边形中任意两点间的线段上的所有点都在多边形内,包括在内部或边界上。不是凸多边形的简单多边形就是凹多边形。如下图,左边是一个凸多边形,右边是一个凹多边形。

:::align{center} :::

现在,给定 个点,满足所有点互不相同,且不存在三个点在同一条直线上。你的任务是选择这 个点中的一些点(可以全选),并按照任意顺序依次连边,最后需要连成一个面积严格大于 。你需要求出能形成的凹多边形的面积最大是多少。

输入格式

第一行一个正整数 (),表示数据组数。

对于每组数据,第一行一个正整数 (),表示点数。

接下来 行,每行两个整数 (),表示各个点的坐标。保证所有点的坐标互不相同,且不存在三点共线。

各个测试数据组的 之和不超过

输出格式

对于每组数据,如果不能形成面积严格大于 的凹多边形,输出 ;否则,输出一个正整数,表示形成的最大的凹多边形的面积的两倍。可以证明这个答案是一个正整数。

样例

样例输入 1

2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1

样例输出 1

40
-1