求点集中面积最大的三角形...显然这个三角形在凸包上...
但是旋转卡壳一般都是一个点卡另一个点...这种要求三角形的情况就要枚举底边的两个点 卡另一个点了...
随着底边点的递增, 最大点显然是在以l(i,j)为底边进行卡壳旋转
但分析了一下这种卡壳的复杂度到了O(n^2) 感觉不太靠谱...不知道有没有更强的方法...我感觉两个点卡的时候都是凸函数...不是很好卡的样子...如果我想到了我再更新这贴...
/********************* Template ************************/ #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <fstream> #include <numeric> #include <iomanip> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define EPS 1e-8 #define MAXN 100005 #define MOD (int)1e9+7 #define PI acos(-1.0) #define INF ((1LL)<<50) #define max(a,b) ((a) > (b) ? (a) : (b)) #define min(a,b) ((a) < (b) ? (a) : (b)) #define max3(a,b,c) (max(max(a,b),c)) #define min3(a,b,c) (min(min(a,b),c)) #define BUG cout<<"BUG! "<<endl #define LINE cout<<"------------------"<<endl #define L(t) (t << 1) #define R(t) (t << 1 | 1) #define Mid(a,b) ((a + b) >> 1) #define lowbit(a) (a & -a) #define FIN freopen("in.txt","r",stdin) #pragma comment (linker,"/STACK:102400000,102400000") // typedef long long LL; // typedef unsigned long long ULL; // typedef __int64 LL; // typedef unisigned __int64 ULL; // int gcd(int a,int b){ return b?gcd(b,a%b):a; } // int lcm(int a,int b){ return a*b/gcd(a,b); } /********************* F ************************/ struct POINT{ double x,y; POINT(double _x = 0, double _y = 0):x(_x),y(_y){}; void show(){ cout<<x<<" "<<y<<endl; } }; POINT p[MAXN],s[MAXN]; double dist(POINT p1,POINT p2){ return((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y)); } double multiply(POINT sp,POINT ep,POINT op){ return (sp.x-op.x) * (ep.y-op.y) - (ep.x-op.x) * (sp.y-op.y); } bool ptcmp(POINT a,POINT b){ // 极角排序cmp p[]为全局变量 if(multiply(a,b,p[0]) == 0) return dist(p[0],a) < dist(p[0],b); return (multiply(a,b,p[0]) > 0); } int Graham_scan(POINT p[],POINT s[],int n){ // 返回凸包点的个数(修改版处理共线,无凸包) int i,k = 0,top = 2; for(i = 1; i < n ; i++) // 取y最小且x最小的点为凸包起点 if((p[i].y < p[k].y) || ((p[i].y == p[k].y) && (p[i].x < p[k].x))) k = i; swap(p[0],p[k]); // 起点设置为p[0] if(n == 2) { // 只有两个点不构成凸包的特判 s[0] = p[0]; s[1] = p[1]; return 2; } sort(p+1,p+n,ptcmp); // 极角排序 for(i = 0 ; i < 3 ; i++) s[i] = p[i]; // 前三个点入栈 if(n == 3 && multiply(s[0],s[1],s[2]) != 0) return 3;// 解决三个点且不共线的bug... while(multiply(s[0],s[top],s[top-1]) == 0 && i < n){ // 前三个点的共线特判 s[top-1] = s[top]; s[top] = p[i++]; } if(i == n){ //所有点都共线的特判 s[1] = s[top]; return 2; } for(; i < n ; i++){ while(multiply(p[i],s[top],s[top-1]) >= 0) top--; s[++top] = p[i]; } return top + 1; } double Triangle_area(POINT a,POINT b,POINT c){ return fabs(multiply(a,b,c)/2); } double Rotation_Calipers(int len){ //旋转卡壳求凸包最大三角形 double ans = 0; for(int i = 0 ; i < len ; i++){ int j = (i + 1) % len; int k = (j + 1) % len; while(j != i && k != i){ ans = max(ans,Triangle_area(s[i],s[j],s[k])); while(Triangle_area(s[i],s[j],s[(k+1)%len]) > Triangle_area(s[i],s[j],s[k])) k = (k + 1) % len; j = (j + 1) % len; } } return ans; } int main() { //freopen("in.txt","r",stdin); //freopen("ou.txt","w",stdout); int n; while(~scanf("%d",&n)){ if(n == -1) break; for(int i = 0 ; i < n ; i++) scanf("%lf%lf",&p[i].x,&p[i].y); int len = Graham_scan(p,s,n); double ans = Rotation_Calipers(len); printf("%.2lf ",ans); } return 0; }