math - 给定n个点。找出面积最大的三角形

Question

给定平面上具有整数坐标的 n 个点。给定点满足条件：上述n个点中的任意3个构成一个三角形。找出面积最大的三角形。

(3 <= n <= 5000, ( -10^8 < xi , yi < 10^8 )

时间限制：2 秒
我无法改进我的代码 - 使用 3 个 for 循环

...

using namespace std;

const int maxn = 5005;
int n, a, b, c;
long long x[maxn], y[maxn], maxS;

long long DienTich(int a, int b, int c){
    return abs((x[b]-x[a]) * (y[c]-y[a]) - (x[c]-x[a]) * (y[b]-y[a]));
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++)
            for (int k = j+1; k <= n; k++)
                if (DienTich(i, j, k) > maxS){
                    maxS = DienTich(i, j, k);
                    a = i; b = j; c = k;
                }
    cout << x[a] << ' ' << y[a] << '\n';
    cout << x[b] << ' ' << y[b] << '\n';
    cout << x[c] << ' ' << y[c];
}

标签： mathgeometry