Skip to content

L3-021 神坛

Statement

Metadata

  • 作者: 邓俊辉
  • 单位: 清华大学
  • 代码长度限制: 16 KB
  • 时间限制: 8000 ms
  • 内存限制: 64 MB

在古老的迈瑞城，巍然屹立着 n 块神石。长老们商议，选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比，因此神坛的面积越小越好。特殊地，如果有两块神石坐标相同，或者三块神石共线，神坛的面积为 0.000。

长老们发现这个问题没有那么简单，于是委托你编程解决这个难题。

输入格式

输入在第一行给出一个正整数 n（3 \le n \le 5000）。随后 n 行，每行有两个整数，分别表示神石的横坐标、纵坐标（-10^9 \le 横坐标、纵坐标 < 10^9）。

输出格式

在一行中输出神坛的最小面积，四舍五入保留 3 位小数。

输入样例 

8
3 4
2 4
1 1
4 1
0 3
3 0
1 3
4 2

输出样例 

0.500

样例解释

输出的数值等于图中红色或紫色框线的三角形的面积。

altar.JPG

鸣谢浙江师范大学伍泰炜补充测试数据！

Solution

#include <bits/stdc++.h>
using namespace std;

#define db double
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define N 5010
int n, m;
int x[N], y[N];
pii cor[N];

ll Cross(pii a, pii b) {
    return abs(1ll * a.fi * b.se - 1ll * b.fi * a.se);
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) scanf("%d%d", x + i, y + i);
        ll res = (ll)1e18;
        for (int i = 1; i <= n; ++i) {
            m = 0;
            for (int j = 1; j <= n; ++j)
                if (i != j) {
                    ++m;
                    cor[m].fi = x[j] - x[i];
                    cor[m].se = y[j] - y[i];
                }
            sort(cor + 1, cor + 1 + m, [](pii a, pii b) {
                return 1ll * a.fi * b.se < 1ll * b.fi * a.se;
            });
            for (int j = 2; j <= m; ++j) res = min(res, Cross(cor[j - 1], cor[j]));
        }
        printf("%.3f\n", res * 0.5);
    }
    return 0;
}
Last update: May 4, 2022
Back to top