#P18183. Palindromic Polygon
Palindromic Polygon
Palindromic Polygon
给定一个具有 个顶点的凸多边形。各顶点按逆时针顺序编号为 ,顶点 上有一个值 。
若某个顶点子集中的值按逆时针顺序排列后,能够通过循环移位变成一个回文序列,就称这个子集是回文的。
形式化地,设选出的 个顶点按逆时针顺序为 。要求存在整数 ,,使得对所有 ,均有
$$f\bigl(v_{(d+i)\bmod k}\bigr)=f\bigl(v_{(d-1-i)\bmod k}\bigr).$$式中的模运算结果取 中的非负整数。
在所有回文顶点子集中,求凸包面积的最大值,输出该最大面积的两倍。只选一个或两个顶点时,面积视为 。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例:
- 第一行一个整数 ;
- 第二行 个整数 ;
- 接下来 行,第 行两个整数 ,表示顶点 的坐标。
顶点按逆时针顺序给出。保证多边形面积为正,任意两个顶点不重合;允许三个或更多顶点共线。
输出格式
每个测试用例输出一行一个整数,表示最大凸包面积的两倍。可以证明这个结果一定是整数。
数据范围
- ;
- ;
- ;
- 同一输入文件内所有测试用例的 之和不超过 。
样例输入
3
8
2 4 2 4 3 4 5 3
2 3
0 6
-3 3
-3 0
-2 -3
1 -5
3 -3
4 0
3
1 2 3
0 0
1 0
0 1
3
1 1 1
0 0
1 0
0 1
样例输出
84
0
1
样例说明
第一个测试用例的原题示意图如下,点旁的数字是该点的 值。

选择顶点 ,按原逆时针顺序得到值序列 。取 ,循环移位后为 ,是回文序列;对应凸包面积为 ,所以输出 。
第二个测试用例三个值互不相同,无法选出面积为正的回文子集,答案为 。第三个测试用例可选全部顶点,面积的两倍为 。