L3-021 神坛 (30 分)-PAT 团体程序设计天梯赛 GPLT

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

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

输入格式：

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

输出格式：

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

输入样例：

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

输出样例：

0.500

分析：A中存储神石的点坐标，B中存储去掉枚举点且排序后，两神石的之间的向量值。枚举每一个点作为起始点，按照极坐标将B排序后，按照向量计算中，三角形面积 = 1/2 * |x1y2 – x2y1|，遍历求出最小神坛面积～

#include <bits/stdc++.h>
using namespace std;
int n, i, cnt;
long long ans = 1e17;
bool cmp (const pair<long long, long long> &a, const pair<long long, long long> &b) {
    if (a.first * b.second != b.first * a.second)
        return a.first * b.second > b.first * a.second;
    return a.first < b.first;
}
int main() {
    scanf("%d", &n);
    vector<pair<long long, long long>> A(n), B(n - 1);
    for (i = 0; i < n; i++) scanf("%lld %lld", &A[i].first, &A[i].second);
    for (i = 0; i < n; i++, cnt = 0) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            B[cnt++] = {A[j].first - A[i].first, A[j].second - A[i].second};
        }
        sort(B.begin(), B.end(), cmp);
        for (int j = 1; j < n - 1; ++j) ans = min(ans, abs(B[j - 1].first * B[j].second - B[j].first * B[j - 1].second));
    }
    printf("%.3f", 0.5 * ans);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, i, cnt;

long long ans = 1e17;

bool cmp (const pair<long long, long long> &a, const pair<long long, long long> &b) {

if (a.first * b.second != b.first * a.second)

return a.first * b.second > b.first * a.second;

return a.first < b.first;

}

int main() {

scanf("%d", &n);

vector<pair<long long, long long>> A(n), B(n - 1);

for (i = 0; i < n; i++) scanf("%lld %lld", &A[i].first, &A[i].second);

for (i = 0; i < n; i++, cnt = 0) {

for (int j = 0; j < n; j++) {

if (i == j) continue;

B[cnt++] = {A[j].first - A[i].first, A[j].second - A[i].second};

}

sort(B.begin(), B.end(), cmp);

for (int j = 1; j < n - 1; ++j) ans = min(ans, abs(B[j - 1].first * B[j].second - B[j].first * B[j - 1].second));

}

printf("%.3f", 0.5 * ans);

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版