YZOJ P3056 三角形最大面积

YZOJ P3056 三角形最大面积

时间限制:1000MS      内存限制:262144KB

出题人:chj2001         难度:\(4.5\)

  • 题目描述

给定平面上 \(n\) 个点,定义 \(f(A,B,C)=\frac{1}{2} \left| x_A(y_B-y_C)+x_B(y_C-y_A)+x_C(y_A-y_B) \right|\) 。

每次操作都会将坐标系顺时针旋转 \(\frac{\pi}{9}\) 弧度,直到与原坐标系重合。

计算每次操作前 \(f\) 的最大值,并输出所有最大值的总和。

  • 输入格式

第一行输入一个正整数 \(n\),表示点的数量;

接下来 \(n\) 行,每行两个整数 \(x_i, y_i\) 表示最开始建立的坐标系下点的坐标。

  • 输出格式

输出所有 \(f\) 最大值的总和。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据,\(3 \leq n \leq 10000, -10000 \leq x_i, y_i \leq 10000\) 。

 

 

 


 

 

 

把 \(f\) 那一堆东西展开然后叉积合并一下,其实就是求 \(A, B, C\) 三点围成三角形的面积。

那本题其实求的就是 \(n\) 个点围成三角形面积的最大值。

很显然这些点一定都会在凸包上,所以把凸包跑出来,然后再 \(O(n^3)\) 暴力就能过。。。。。。。。。。

好吧,很显然这个做法很容易会被卡掉。

注意到固定两个点时,移动其中一个点,最大值对应的第三个点的移动也是单调的。

于是就可以跑一个旋(xuán)转(zhuǎn)卡(qiǎ)壳(ké),本质上就是维护第三个点的单调移动

然后就是 \(O(n^2)\) 了,貌似xx论文(国集?)里有证明:平面内坐标范围在 \([0, r]\) 内的点构成的凸包点数为 \(O(r^{\frac{2}{3}})\),然后就能过了。

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注