题目链接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=1069
(luogu)https://www.luogu.org/problemnew/show/P4166
题解: 水题，凸包极角排序之后枚举凸四边形对角线\(i,j\)然后找面积最大的点\(k\)，\(k\)随着\(i,j\)是单调的
但是有个易错点，就是双指针那个\(k\)前移的条件必须是前移后大于等于原来，如果写成大于就只有50(详见代码)
查了半天发现原因居然是: 数据里有重点! 一旦有重点就会出现\(k\)一直在重点处进不动的情况。呜呜呜好坑啊
代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<algorithm>
#include<cmath>
using namespace std;const double EPS = 1e-8;
int dcmp(double x) {return x<-EPS ? -1 : (x>EPS ? 1 : 0);}
struct Point
{double x,y;Point() {}Point(double _x,double _y) {x = _x,y = _y;}
};
bool cmpy(Point x,Point y) {return dcmp(x.y-y.y)<0 || (dcmp(x.y-y.y)==0 && dcmp(x.x-y.x)<0);}
bool cmpx(Point x,Point y) {return dcmp(x.x-y.x)<0 || (dcmp(x.x-y.x)==0 && dcmp(x.y-y.y)<0);}
typedef Point Vector;
Point operator +(Point x,Point y) {return Point(x.x+y.x,x.y+y.y);}
Point operator -(Point x,Point y) {return Point(x.x-y.x,x.y-y.y);}
Point operator *(Point x,double y) {return Point(x.x*y,x.y*y);}
Point operator /(Point x,double y) {return Point(x.x/y,x.y/y);}
double Dot(Vector x,Vector y) {return x.x*y.x+x.y*y.y;}
double Cross(Vector x,Vector y) {return x.x*y.y-x.y*y.x;}
double EuclidDist(Point x,Point y) {return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
Vector rotate(Vector x,double ang) {return Vector(x.x*cos(ang)-x.y*sin(ang),x.x*sin(ang)+x.y*cos(ang));}
const int N = 2000;
Point a[N+3];
Point ch[(N<<1)+3];
int stk[N+3];
double area[N+3][N+3];
int n,tp;bool cmp(Point x,Point y) {return dcmp(Cross(x-a[1],y-a[1]))>0;}void Convex_Hull()
{for(int i=2; i<=n; i++){if(cmpy(a[i],a[1])==true) {swap(a[i],a[1]);}}sort(a+2,a+n+1,cmp);stk[1] = 1; stk[2] = 2; tp = 2;for(int i=3; i<=n; i++){while(dcmp(Cross(a[i]-a[stk[tp-1]],a[stk[tp]]-a[stk[tp-1]]))>0) {tp--;}tp++; stk[tp] = i;}for(int i=1; i<=tp; i++) ch[i] = a[stk[i]];for(int i=1; i<=tp; i++) ch[i+tp] = ch[i];
// printf("chsize=%d\n",tp);
// for(int i=1; i<=tp; i++) printf("(%lf %lf)\n",ch[i].x,ch[i].y);
}int main()
{scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%lf%lf",&a[i].x,&a[i].y);Convex_Hull();if(tp==3){double ans = fabs(Cross(ch[2]-ch[1],ch[3]-ch[1]))/2.0,ans2 = 1e11;for(int i=1; i<=n; i++){if(i==stk[1]||i==stk[2]||i==stk[3]) continue;double cur = min(min(fabs(Cross(a[i]-ch[1],ch[2]-ch[1])),fabs(Cross(a[i]-ch[2],ch[3]-ch[2]))),fabs(Cross(a[i]-ch[3],ch[1]-ch[3])))/2.0;ans2 = min(ans2,cur);}printf("%lf\n",ans-ans2);return 0;}double ans = 0.0;for(int i=1; i<=tp; i++){int k = i+1;for(int j=i+2; j<=i+tp-2; j++){while(k+1<j && dcmp(Cross(ch[k+1]-ch[i],ch[j]-ch[i])-Cross(ch[k]-ch[i],ch[j]-ch[i]))>=0) {k++;}area[i][(j-1)%tp+1] = Cross(ch[k]-ch[i],ch[j]-ch[i])/2.0;
// printf("i%d j%d k%d %lf\n",i,j,k,area[j]);}}for(int i=1; i<=tp; i++){for(int j=i+2; j<=tp; j++){double tmp = area[i][j]+area[j][i];
// printf("area[%d][%d]=%lf\n",i,j,area[i][j]);
// printf("area[%d][%d]=%lf\n",j,i,area[j][i]);ans = max(ans,tmp);}}printf("%.3lf\n",ans);return 0;
}
