现在的位置: 首页 > 综合 > 正文

PKU2079 Triangle 点集最大三角形面积

2013年02月16日 ⁄ 综合 ⁄ 共 2225字 ⁄ 字号 评论关闭

题意:给定一些点,要求找出由这些点集构成的最大三角形面积。

分析:最大三角形的三个顶点必定在凸包上。求出凸包上的点后,枚举各种组合,得到最大面积。

朴素算法的时间复杂度是(n^3),但可根据凸包的单峰性进行剪枝。这里用到Rotating Calipers algorithm

枚举三角形的第一个顶点i,

然后初始第二个顶点j=i+1,第三个顶点k=j+1,

循环k+1直到Area(i,j,k)>Area(i,j,k+1)

更新面积的最大值,下面就开始旋转卡壳了(旋转j,k两个点)

(1)如果Area(i,j,k)<Area(i,j,k+1)且k!=i,则k=k+1,否则转(2)

(2)更新面积,j=j+1,如果j=i,跳出循环

这样旋转一圈后,求得的面积就是以i为顶点的最大三角形的面积了。

时间复杂度是O(n^2)

题目链接:http://poj.org/problem?id=2079

代码

//Rotating Calipers algorithm
#include <stdio.h>
#include
<stdlib.h>
#include
<math.h>
#define MaxNode 50005
int stack[MaxNode];
int top;
double max;

struct TPoint {
double x,y;
} 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
*c = (TPoint *) a;
TPoint
*d = (TPoint *) b;
double k = multi(*c, *d, point[0]);
if (k < 0) return 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 - 1, sizeof (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 == 0) break;
}
top
++;
stack[top]
= i;
}
}

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;
}

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(
"%lf%lf", &point[i].x, &point[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;
}

抱歉!评论已关闭.