P16931 星界碑针

:::info[题目背景] 随着几座「拱辰封仪」轰然倒塌，环绕「沉星书库」的那层古老封锁终于出现了缺口。 最先发生变化的是空气。原本盘踞在四周、沉重得几乎令人难以呼吸的魔力，像退潮一样缓缓散开。紧接着，「沉星书库」那两扇尘封已久的高门发出低沉而漫长的轰鸣，仿佛某种沉睡了太久的巨物，终于在岁月深处睁开了眼睛。石门向两侧缓缓敞开，细碎的灰尘从门缝间簌簌落下，在斜照进来的天光里浮动，像一场安静而迟缓的雪。 「打开了……」菲伦轻声说道。 门后并不是想象中的狭长回廊，而是一片异常宽阔的前庭。 地面由整块整块灰白色的古石铺成，其上布满了极细的纹路，像是某种被磨损了无数年的星图。前庭中散布着许多高低不一的黑色石柱，有些已经倾斜断裂，有些仍安静地立着，柱顶镶嵌着黯淡的晶核。若从近处看去，会发现每一根石柱下方都刻着极古老的术式文字，彼此之间又以肉眼几乎无法察觉的魔力细线悄然相连。 「这些也是机关吗？」休塔尔克皱起眉。 「嗯。」芙莉莲点了点头，目光从那些散落四处的石柱上缓缓掠过，「这些叫作『星界碑针』。古代魔法使会把它们当作观测与定界的节点。单独看时没什么特别，但一旦有足够多的碑针被激活，它们就会自动连成外沿，张开覆盖整片前庭的边界结界。」 菲伦顺着她的视线望去。果然，随着书库大门开启，部分沉寂已久的碑针也开始逐一点亮。幽蓝色的光从柱顶缓慢浮现，像夜色里被依次唤醒的寒星。那些亮起的节点之间，不断有纤细的光线彼此勾连、延展，描出一条条尚未稳定的轮廓。 「而且，这个结界还在变化。」芙莉莲轻声说道。 有些碑针因为年代久远，才亮起不久便再次黯淡下去；也有新的碑针被书库内部逸散出的魔力重新唤醒。每当一处节点发生变化，前庭上空那层淡淡的光幕便会随之重绘边缘，时而向外扩展，时而向内收拢，像一张正在不断改写形状的透明地图。 「也就是说……」休塔尔克看着那些忽明忽暗的光点，神情逐渐变得复杂起来，「我们得一直弄清楚，现在最外面的那圈到底围出了多大一片地方？」 「嗯。」芙莉莲的语气依旧平静，「只要知道当前所有有效的『星界碑针』中，最外围的边界是怎样连接的，就能算出这层结界此刻覆盖的范围。」 她微微抬起头，望着前庭上方那条仍在变化的光之轮廓。

书库前庭的地面可以看作一个笛卡尔坐标系，上面坐落了 $n$ 个「星界碑针」，编号 $1\sim n$，其中 $n$ 为偶数。第 $i$ 个「星界碑针」的坐标为 $(x_i, y_i)$。保证所有「星界碑针」的坐标两两不同，且不存在三点共线。 芙莉莲已经破解了「星界碑针」的明暗变化，具体的，对于任意角度 $\theta\in[0,\pi)$，定义方向向量 $u_\theta=(\cos\theta,\sin\theta)$，则对每个「星界碑针」 $P_i=(x_i,y_i)$，定义它在该方向上的投影值为 $p_i(\theta)=x_i\cos\theta+y_i\sin\theta$，如果在该角度下**所有 $p_i(\theta)$ 两两不同**，则称该角度为「星界角」。 对于一个「星界角」 $\theta$，将所有「星界碑针」的坐标按投影后的结果 $p_i(\theta)$ 从小到大排序，则前 $\frac{n}{2}$ 个「星界碑针」将会亮起，记这些「星界碑针」的凸包面积为 $A_\theta$。 芙莉莲需要知道最大的「星界碑针」凸包面积的两倍，也就是 $$S=\max_{\theta\ \text{为「星界角」}} 2A_\theta $$ 由于坐标均为整数，因此可以保证该答案为整数。

输入第一行包含整数 $n(2\leq n\leq 2\times 10^3)$，代表「星界碑针」的数量。 第 $i$ 行包含两个整数 $x_i, y_i(-10^6\leq x_i, y_i\leq 10^6)$，代表第 $i$ 个「星界碑针」的坐标。

输出一个整数，代表最大的「星界碑针」凸包面积的两倍 $$S=\max_{\theta\ \text{为「星界角」}} 2A_\theta $$