Title
https://www.luogu.com.cn/problem/P4166
Solution
先求凸包,然后枚举点 i i i,然后对于点 j j j得到的 i i i与 j j j(有序)中间的点,以及 j j j与 i i i(有序)中间的点,都是单调的
- 先用 G r a h a m Graham Graham算法求凸包
- 然后枚举四边形的对角线,剩下的两个点 a , b a,b a,b可以根据旋转卡壳的思想巧妙得到,因为决策单调性,每次枚举下一个 j j j时, a , b a,b a,b最远点可以从这次的位置继续同向枚举。
- 时间复杂度 O ( N l o g 2 N + N 2 ) ≈ O ( N 2 ) O(Nlog_{2}N+N^2) \approx O(N^2) O(Nlog2N+N2)≈O(N2)
Code
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=2005;
double ans=0;
struct point{double x,y; point operator - (point&s){return (point){x-s.x,y-s.y};}
}P[maxn],t[maxn];
double operator *(point a,point b){return a.x*b.y-b.x*a.y;
}
int n,sta[maxn],top;
inline double dist2(point P1,point P2){return (P1.x-P2.x)*(P1.x-P2.x)+(P1.y-P2.y)*(P1.y-P2.y);
}
inline bool judgeOnLeft(point p0,point p1,point p2){double s=(p1-p0)*(p2-p0); return s<0||(s==0&&dist2(p1,p0)>=dist2(p2,p0));
}
inline bool cmp(point p1,point p2){double s=(p1-P[1])*(p2-P[1]); return s<0||(s==0&&dist2(p1,P[0])>=dist2(p2,P[0]));
}
inline int Graham(){sort(&P[2],&P[n+1],cmp); P[n+1]=P[1]; sta[1]=1; sta[2]=2; top=2; for(int i=3;i<=n+1;i++){while(top>1&&judgeOnLeft(P[sta[top-1]],P[i],P[sta[top]])) top--; sta[++top]=i; }top--;return top;
}
inline double solve(){if (n<2) return 0; sta[n+1]=sta[1]; for(int i=1;i<=n+1;i++) t[i]=P[sta[i]]; for(int i=1;i<=n;i++){int a=i,b=i+1; for(int j=i;j<=n;j++){while ((t[j]-t[i])*(t[a+1]-t[i])-(t[j]-t[i])*(t[a]-t[i])>0) a=a%n+1; while ((t[b+1]-t[i])*(t[j]-t[i])-(t[b]-t[i])*(t[j]-t[i])>0) b=b%n+1; ans=max(ans,(t[j]-t[i])*(t[a]-t[i])+(t[b]-t[i])*(t[j]-t[i])); }}return ans/2;
}
int main(){scanf("%d",&n); int First=1; for(int i=1;i<=n;i++) {scanf("%lf%lf",&P[i].x,&P[i].y); if (P[i].x<P[First].x||(P[i].x==P[First].x&&P[i].y<P[First].y)) First=i; }swap(P[First],P[1]); n=Graham(); return 0&printf("%.3lf\n",solve());
}