题目大意:
二维平面有N个点,选择其中的任意四个点使这四个点围成的多边形面积最大
题解:
很容易发现这四个点一定在凸包上
所以我们枚举一条边再旋转卡壳确定另外的两个点即可旋(xuan2)转(zhuan4)卡(qia3)壳(ke2)#include#include #include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;char ch;bool flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}inline int cat_max(const int &a,const int &b){return a>b ? a:b;}inline int cat_min(const int &a,const int &b){return a -eps) return 0; return x > 0 ? 1 : -1;}struct Point{ double x,y; Point(double a = .0,double b = .0){ x=a;y=b; }};typedef Point Vector;Vector operator + (const Vector &a,const Vector &b){ return Vector(a.x + b.x,a.y + b.y);}Vector operator - (const Vector &a,const Vector &b){ return Vector(a.x - b.x,a.y - b.y);}double operator * (const Vector &a,const Vector &b){ return a.x*b.x + a.y*b.y;}double operator ^ (const Vector &a,const Vector &b){ return a.x*b.y - a.y*b.x;}double trigonArea(const Point &a,const Point &b,const Point &c){ return abs((b - a)^(c - a))/2.0;}inline bool cmp(const Point &a,const Point &b){ return dcmp(a.x - b.x) == 0 ? a.y < b.y : a.x < b.x;}Point p[maxn],ch[maxn];int m = 0,n;void convex(){ sort(p+1,p+n+1,cmp);m = 0; for(int i=1;i<=n;++i){ while(m > 1 && dcmp((ch[m] - ch[m-1])^(p[i] - ch[m])) <= 0) -- m; ch[++m] = p[i]; }int k = m; //printf("%d\n",k); for(int i=n-1;i>=1;--i){ while(m > k && dcmp((ch[m] - ch[m-1])^(p[i] - ch[m])) <= 0) -- m; ch[++m] = p[i]; }if(n > 1) -- m; //printf("%d\n",m); swap(n,m);swap(p,ch);}#define nx(x) ((x) % n + 1)double spinClipShell(){ double ret = .0;p[n+1] = p[1]; for(int i=1;i<=n;++i){ int x = nx(i); int y = nx(i+2); for(int j=i+2;j<=n;++j){ while((nx(x) != j) && dcmp(trigonArea(p[x],p[i],p[j]) - trigonArea(p[x+1],p[i],p[j])) < 0) x = nx(x); while((nx(y) != i) && dcmp(trigonArea(p[y],p[i],p[j]) - trigonArea(p[y+1],p[i],p[j])) < 0) y = nx(y); ret = max(ret,trigonArea(p[x],p[i],p[j]) + trigonArea(p[y],p[i],p[j])); } }return ret;}int main(){ read(n); for(int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y); convex();printf("%.3lf\n",spinClipShell()); getchar();getchar(); return 0;}