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\) 最大值的总和。
-
样例输入
|
1 2 3 4 5 6 7 |
6 0 0 1 3 3 1 1 9 9 1 9 9 |
-
样例输出
|
1 |
720 |
-
数据规模与约定
对于 \(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}})\)，然后就能过了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm> typedef long long LLONG; #define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_)) inline int getnum() { register char c=0; register bool neg=false; while(!(c>='0' && c<='9')) c=getchar(),neg|=(c=='-'); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return (neg?-1:1)*a; } struct _point { int x,y; bool operator < (const _point&o)const { if(x != o.x) return x<o.x; return y<o.y; } inline int operator * (const _point&o)const { return x*o.y - y*o.x; } inline _point operator - (const _point&o)const { return (_point){x-o.x, y-o.y}; } }p[10505]; int stk[10505],lst[10505],llst; bool vis[10505]; int main() { register int N=getnum(); for(register int i=1;i<=N;i++) p[i].x=getnum(),p[i].y=getnum(); std::sort(&p[1],&p[N+1]); register int top=0; for(register int i=1;i<=N;i++) { while(top>=2 && (p[stk[top]]-p[stk[top-1]])*(p[i]-p[stk[top-1]])>=0) top--; stk[++top]=i; } while(top) lst[++llst]=stk[top],vis[stk[top]]=true,top--; for(register int i=N;i>=1;i--) { while(top>=2 && (p[stk[top]]-p[stk[top-1]])*(p[i]-p[stk[top-1]])>=0) top--; stk[++top]=i; } while(top) (!vis[stk[top]] ? lst[++llst]=stk[top], vis[stk[top]]=true : 0),top--; register int ans=0; for(register int i=1;i<llst-1;i++) for(register int j=i+1,k=j;j<llst;j++) { reju: register int t=(p[lst[k]]-p[lst[i]])*(p[lst[j]]-p[lst[i]]); if(t<0) t=-t; register int t1=(p[lst[k+1]]-p[lst[i]])*(p[lst[j]]-p[lst[i]]); if(t1<0) t1=-t1; if(t1>t) { k++,t=t1; goto reju; } ans=_max(ans,t); } printf("%lld\n",(long long)ans*9); return 0; } |