#P18183. Palindromic Polygon

Palindromic Polygon

Palindromic Polygon

给定一个具有 nn 个顶点的凸多边形。各顶点按逆时针顺序编号为 1,2,…,n1,2,\ldots,n,顶点 ii 上有一个值 f(i)f(i)。

若某个顶点子集中的值按逆时针顺序排列后,能够通过循环移位变成一个回文序列,就称这个子集是回文的。

形式化地,设选出的 kk 个顶点按逆时针顺序为 v0,v1,…,vk−1v_0,v_1,\ldots,v_{k-1}。要求存在整数 dd,0≤d<k0\le d<k,使得对所有 0≤i<k0\le i<k,均有

$$f\bigl(v_{(d+i)\bmod k}\bigr)=f\bigl(v_{(d-1-i)\bmod k}\bigr).$$

式中的模运算结果取 0,1,…,k−10,1,\ldots,k-1 中的非负整数。

在所有回文顶点子集中,求凸包面积的最大值,输出该最大面积的两倍。只选一个或两个顶点时,面积视为 00。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例:

  • 第一行一个整数 nn;
  • 第二行 nn 个整数 f(1),f(2),…,f(n)f(1),f(2),\ldots,f(n);
  • 接下来 nn 行,第 ii 行两个整数 xi,yix_i,y_i,表示顶点 ii 的坐标。

顶点按逆时针顺序给出。保证多边形面积为正,任意两个顶点不重合;允许三个或更多顶点共线。

输出格式

每个测试用例输出一行一个整数,表示最大凸包面积的两倍。可以证明这个结果一定是整数。

数据范围

  • 3≤n≤5003\le n\le500;
  • 1≤f(i)≤1091\le f(i)\le10^9;
  • −109≤xi,yi≤109-10^9\le x_i,y_i\le10^9;
  • 同一输入文件内所有测试用例的 nn 之和不超过 10001000。

样例输入

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

样例说明

第一个测试用例的原题示意图如下,点旁的数字是该点的 ff 值。

第一个样例:蓝色区域为所选顶点的凸包

选择顶点 2,4,5,6,82,4,5,6,8,按原逆时针顺序得到值序列 (4,4,3,4,3)(4,4,3,4,3)。取 d=1d=1,循环移位后为 (4,3,4,3,4)(4,3,4,3,4),是回文序列;对应凸包面积为 4242,所以输出 8484。

第二个测试用例三个值互不相同,无法选出面积为正的回文子集,答案为 00。第三个测试用例可选全部顶点,面积的两倍为 11。