首页 > 代码库 > HDU2202--最大三角形（凸包，枚举）

HDU2202--最大三角形（凸包，枚举）

2024-08-31 23:06:24   217人阅读

Problem Description

老师在计算几何这门课上给Eddy布置了一道题目，题目是这样的：给定二维的平面上n个不同的点，要求在这些点里寻找三个点，使他们构成的三角形拥有的面积最大。
Eddy对这道题目百思不得其解，想不通用什么方法来解决，因此他找到了聪明的你，请你帮他解决这个题目。

Input

输入数据包含多组测试用例，每个测试用例的第一行包含一个整数n，表示一共有n个互不相同的点，接下来的n行每行包含2个整数xi,yi，表示平面上第i个点的x与y坐标。你可以认为：3 <= n <= 50000 而且 -10000 <= xi, yi <= 10000.

Output

对于每一组测试数据，请输出构成的最大的三角形的面积，结果保留两位小数。
每组输出占一行。

Sample Input

3
3 4
2 6
3 7
6
2 6
3 9
2 0
8 0
6 6
7 7

Sample Output

1.50
27.00

Author

Eddy

Recommend

lcy

思路：

最大三角形的三个点一定在点的凸包上，求出凸包之后，直接暴力枚举点即可

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 55000;
const int INF = 0x3f3f3f3f;
const int eps = 1e-8;
int sgn(double x)//判断浮点数x的符号,0返回0，正数返回1，负数返回-1
{
    if (fabs(x) < eps)return 0;
    if (x < 0)return -1;
    else return 1;
}
struct Point
{
    int x, y;
    Point() {}
    Point(int _x, int _y)
    {
        x = _x; y = _y;
    }
    Point operator -(const Point &b)const
    {
        return Point(x - b.x, y - b.y);
    }

    double operator ^(const Point &b)const //叉积
    {
        return x * b.y - y * b.x;
    }

    double operator *(const Point &b)const //点积
    {
        return x * b.x + y * b.y;
    }
    bool operator ==(const Point &b)const
    {
        return (x == b.x) && (y == b.y);
    }
    bool operator !=(const Point&b)const
    {
        return (x != b.x) || (y != b.y);
    }
    void input() { //点的输入
        scanf("%d%d", &x, &y);
    }
};
struct Line {
    Point s, e;
    Line() {}
    Line(Point _s, Point _e) {
        s = _s; e = _e;
    }
};

double dist(Point& a, Point& b) //*两点间距离
{
    return sqrt((a - b) * (a - b));
}
Point zero;
int k;
bool cmp(Point& a, Point &b)
{
    double tmp = (a - zero) ^ (b - zero);
    if (sgn(tmp) > 0) {
        return 1;
    }
    if (sgn(tmp) == 0 && sgn(dist(a, zero) - dist(b, zero)) <= 0)
        return 1;
    return 0;
}
int n;
Point a[MAXN];
int l[MAXN];
int cou = 0;
void Gram()
{
    cou = 0;
    swap(a[0], a[k]);
    sort(a + 1, a + n, cmp);
    if (n == 1) {
        l[cou++] = 0;
        return;
    }
    if (n == 2) {
        l[cou++] = 0;
        l[cou++] = 1;
        return;
    }
    l[cou++] = 0;
    l[cou++] = 1;
    for (int i = 2; i < n; i++) {
        while (sgn((a[i] - a[l[cou - 2]]) ^ (a[l[cou - 1]] - a[l[cou - 2]])) != -1) {
            cou--;
        }
        l[cou++] = i;
    }
}
int main()
{
    //freopen("data.in", "r", stdin);
    while (~scanf("%d", &n)) {
        zero.x = zero.y = INF;
        for (int i = 0; i < n; i++) {
            a[i].input();
            if (a[i].y < zero.y) {
                zero.x = a[i].x;
                zero.y = a[i].y;
                k = i;
            }
            else if (a[i].y == zero.y) {
                if (a[i].x < zero.x) {
                    zero.x = a[i].x;
                    zero.y = a[i].y;
                    k = i;
                }
            }
        }
        Gram();
        double res = -3;
        for (int i = 0; i < cou; i++) {
            for (int j = 0; j < cou; j++) {
                for (int k = 0; k < cou; k++) {
                    double tmp = fabs((a[l[i]] - a[l[j]]) ^ (a[l[k]] - a[l[j]]));
                    if (tmp > res) {
                        res = tmp;
                    }
                }
            }
        }
        res = res / 2 ;
        printf("%.2lf\n", res);
    }
}

HDU2202--最大三角形（凸包，枚举）


联系
我们