L3-021 神坛 (30 分)-PAT 团体程序设计天梯赛 GPLT
程序员文章站
2022-04-01 11:22:05
...
在古老的迈瑞城,巍然屹立着 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;
}
上一篇: 微信小程序换肤功能实现代码(思路详解)
下一篇: 微信小程序实现身份证取景框拍摄