题目链接
题解
首先四个点一定在凸包上
我们枚举对角线，剩下两个点分别是两侧最远的点
可以三分，复杂度\(O(n^2logn)\)
可以借鉴旋转卡壳的思想，那两个点随着对角线的一定单调不减，可以用两个指针维护，复杂度\(O(n^2)\)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 2005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
struct point{double x,y;}p[maxn],t[maxn];
inline bool operator <(const point& a,const point& b){
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
inline point operator +(const point& a,const point& b){
return (point){a.x + b.x,a.y + b.y};
}
inline point operator -(const point& a,const point& b){
return (point){a.x - b.x,a.y - b.y};
}
inline double operator *(const point& a,const point& b){
return a.x * b.x + a.y * b.y;
}
inline double cross(const point& a,const point& b){
return a.x * b.y - a.y * b.x;
}
inline double dis(const point& a,const point& b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
inline double S(const point& a,const point& b,const point& c){
return fabs(0.5 * cross(c - a,c - b));
}
int n,st[maxn],top;
void cal(){
sort(p + 1,p + 1 + n);
st[top = 1] = 1;
for (int i = 2; i <= n; i++){
while (top > 1 && cross(p[i] - p[st[top]],p[st[top]] - p[st[top - 1]]) <= 0)
top--;
st[++top] = i;
}
int tmp = top;
for (int i = n - 1; i; i--){
while (top > tmp && cross(p[i] - p[st[top]],p[st[top]] - p[st[top - 1]]) <= 0)
top--;
st[++top] = i;
}
n = --top;
for (int i = 1; i <= n; i++) t[i] = p[st[i]];
for (int i = 1; i <= n; i++) p[i] = t[i];
}
void solve(){
if (n == 3){printf("%.3lf",S(p[1],p[2],p[3])); return;}
double ans = 0;
for (int i = 1; i <= n - 3; i++){
int x = i + 1,y = i + 3;
for (int j = i + 3; j <= n; j++){
if (S(p[i],p[i + 2],p[j]) > S(p[i],p[i + 2],p[y]))
y = j;
}
ans = max(ans,S(p[i],p[i + 2],p[x]) + S(p[i],p[i + 2],p[y]));
for (int j = i + 3; j <= n; j++){
while (x + 1 < j && S(p[i],p[j],p[x + 1]) > S(p[i],p[j],p[x])) x++;
while (y + 1 <= n && S(p[i],p[j],p[y + 1]) > S(p[i],p[j],p[y])) y++;
ans = max(ans,S(p[i],p[j],p[x]) + S(p[i],p[j],p[y]));
}
}
printf("%.3lf\n",ans);
}
int main(){
n = read();
if (n <= 2) {puts("0"); return 0;}
REP(i,n) scanf("%lf%lf",&p[i].x,&p[i].y);
cal();
//REP(i,n) printf("(%lf,%lf)\n",p[i].x,p[i].y);
solve();
return 0;
}