题意：二面平面，给N个点，求最大三角形。
分析：先求凸包降低数据规模，最大三角形肯定是凸包的点，然后枚举凸包的各点求三角形。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
const int MAXN = 50005;
int stack[MAXN];
int top;
typedef struct Point
{
int x,y;
}Point;
Point points[MAXN];
double cross(Point p1, Point p2, Point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double distance(Point p1, Point 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){
Point *p1 = (Point*)a;
Point *p2 = (Point*)b;
double res = cross(*p1, *p2, points[0]);
if(res>0)
return -1;
else if(res==0 && distance(points[0], *p1) >(distance(points[0], *p2)) )
return -1;
else
return 1;
}
void swap(Point point[], int i, int j){
Point tmp;
tmp = point[i];
point[i] = point[j];
point[j] = tmp;
}
void grahamScan(int n){
//Graham扫描求凸包
int i, u;
//将最左下的点调整到p[0]的位置
u = 0;
for(i = 1;i <= n - 1;i++){
if((points[i].y < points[u].y) ||
(points[i].y == points[u].y && points[i].x < points[u].x))
u = i;
}
swap(points, 0, u);
//将平p[1]到p[n - 1]按按极角排序，可采用快速排序
qsort(points+1, n-1, sizeof(points[0]), cmp);
for(i = 0;i <= 2;i++) stack[i] = i;
top = 2;
for(i = 3;i <= n - 1;i++){
while(cross(points[i], points[stack[top-1]], points[stack[top]]) < 0){
top--;
if(top == 0) break;
}
top++;
stack[top] = i;
}
}
double triangleArea(int i, int j, int k){
//已知三角形三个顶点的坐标，求三角形的面积
double l = fabs((double)(points[i].x * points[j].y + points[j].x * points[k].y
+ points[k].x * points[i].y - points[j].x * points[i].y
- points[k].x * points[j].y - points[i].x * points[k].y))/2;
return l;
}
double max;
void PloygonTriangle(){
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++;
}
}
}
}
int main(){
int i,n;
while(scanf("%d", &n) && n!=-1){
for(i=0; i<n; ++i)
scanf("%d%d", &points[i].x, &points[i].y );
if(n<=2){
printf("0.00\n");
continue;
}
if(n==3){
printf("%.2lf\n", triangleArea(0,1,2));
continue;
}
grahamScan(n);
PloygonTriangle();
printf("%.2lf\n", max);
}
return 0;
}
posted on 2011-04-26 20:55
小阮 阅读(559)
评论(0) 编辑 收藏 引用 所属分类:
计算几何