随笔-141  评论-9  文章-3  trackbacks-0
先求凸包, 最大三角形的三个顶点一定在凸包的点上.
//Rotating Calipers algorithm


#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<math.h>

#define MaxNode 50005

int stack[MaxNode];
int top;
double max;

typedef 
struct TPoint
{
    
int x;
    
int y;
}
TPoint;
TPoint point[MaxNode];

void swap(TPoint point[], int i, int j)
{
    TPoint tmp;
    tmp 
= point[i];
    point[i] 
= point[j];
    point[j] 
= tmp;
}


double multi(TPoint p1, TPoint p2, TPoint p0)
{
    
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}


double distance(TPoint p1, TPoint p2)
{
    
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}


int cmp(const void *a, const void *b)
{
    TPoint 
*= (TPoint *)a;
    TPoint 
*= (TPoint *)b;
    
double k = multi(*c, *d, point[0]);
    
if(k< 0return 1;
    
else if(k == 0 && distance(*c, point[0]) >= distance(*d, point[0]))  
            
return 1;
    
else return -1;   
}


void grahamScan(int n)

    
//Graham扫描求凸包
    int i, u; 
    
    
//将最左下的点调整到p[0]的位置
    u = 0;
    
for(i = 1;i <= n - 1;i++){
        
if((point[i].y < point[u].y) || 
             (point[i].y 
== point[u].y && point[i].x  < point[u].x))
            u 
= i;      
    }
 
    swap(point, 
0, u);
    
    
//将平p[1]到p[n - 1]按按极角排序,可采用快速排序
    qsort(point + 1, n - 1sizeof(point[0]), cmp);
    
    
for(i = 0;i <= 2;i++) stack[i] = i;
    top 
= 2;
    
for(i = 3;i <= n - 1;i++){
        
while(multi(point[i], point[stack[top]], point[stack[top - 1]]) >= 0){
            top
--;
            
if(top == 0break;
        }

        top
++;
        stack[top] 
= i;
    }

}


int main()
{    
    
double triangleArea(int i, int j, int k);
    
void PloygonTriangle();
    
int i, n;
    
while(scanf("%d"&n) && n != -1){
        
for(i = 0;i < n;i++)
            scanf(
"%d%d"&point[i].x, &point[i].y);
        
if(n <= 2){
            printf(
"0.00\n");
            
continue;      
        }

        
if(n == 3){
            printf(
"%.2lf\n", triangleArea(012));
            
continue
        }

        grahamScan(n);
        PloygonTriangle();    
        printf(
"%.2lf\n", max);    
    }

    
return 0;
}


void PloygonTriangle()
{
    
double triangleArea(int i, int j, int k);
    
int i, j , k;
    
double area, area1;
    max 
= -1;
    
for(i = 0;i <= top - 2;i++)
        k 
= -1;
        
for(j = i + 1; j <= top - 1;j++)
            
if(k <= j) k= j + 1;
            area 
= triangleArea(stack[i], stack[j], stack[k]);
            
if(area > max) max = area;
            
while(k + 1 <= top){
                area1
= triangleArea(stack[i], stack[j], stack[k + 1]);
                
if(area1 < area) break;
                
if(area1 > max) max = area1;
                area 
= area1;
                k
++;
            }

        }

    }

}


double triangleArea(int i, int j, int k)
{
    
//已知三角形三个顶点的坐标,求三角形的面积 
    double l = fabs(point[i].x * point[j].y + point[j].x * point[k].y 
        
+ point[k].x * point[i].y - point[j].x * point[i].y 
        
- point[k].x * point[j].y - point[i].x * point[k].y) / 2;  
    
return l;
}




posted on 2011-06-30 20:37 小阮 阅读(2015) 评论(0)  编辑 收藏 引用 所属分类: 计算几何

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理