POJ 2079 Triangle 旋转卡壳求最大三角形-白红宇

POJ 2079 Triangle 旋转卡壳求最大三角形

阅读量：4330 次

发布时间：2019-06-06

本文共 2841 字，大约阅读时间需要 9 分钟。

求点集中面积最大的三角形...显然这个三角形在凸包上...

但是旋转卡壳一般都是一个点卡另一个点...这种要求三角形的情况就要枚举底边的两个点卡另一个点了...

随着底边点的递增, 最大点显然是在以l(i,j)为底边进行卡壳旋转

但分析了一下这种卡壳的复杂度到了O(n^2) 感觉不太靠谱...不知道有没有更强的方法...我感觉两个点卡的时候都是凸函数...不是很好卡的样子...如果我想到了我再更新这贴...

/********************* Template ************************/#include 
     
      #include 
      #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         
                          #include 
                          
                           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! "<
                           
                            > 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<
                            
                             <<" "<
                             
                              <
                              
                                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\n",ans); } return 0;}