【编程】平面点集构成三角形的最小(大)周长(面积)
* 持续更新中 *
题目
空间中有n个点(x,y),求其中三个点构成三角形的最小(大)周长(面积)。
测试用例
说明
n个点不存在重复现象 输入点的个数 3<= n < 2000, 接下来n行数据 -10000 <= x,y <= 10000 0结束测试数据
输入
7 1 0 2 0 0 2 2 3 0 1 3 0 0 3 3 3 4 2 6 3 7 4 -5 -5 -4 3 4 1 3 -2 0
输出
0.0 4.0 1.5 1.5 10.5 33.0
代码
暴力解题
时间复杂度 O(n^3)
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <iomanip> using namespace std; namespace my { struct Point { int x = 0; int y = 0; Point() {} Point(int a, int b) { x = a; y = b; } inline double dis(const Point& p) { return (p.x - x) * (p.x - x) + (p.y - y) * (p.y - y); } }; inline double area(const Point& p1, const Point& p2, const Point& p3) { return abs((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)) * 0.5; } } int main() { my::Point pos[2000]; freopen("data.txt", "r", stdin); while (1) { int n = 0; cin >> n; if (n == 0) break; for (size_t i = 0; i < n; i++) { cin >> pos[i].x >> pos[i].y; } double minVal = DBL_MAX; double maxVal = DBL_MIN; for (size_t i = 0; i < n; i++) { for (size_t j = i + 1; j < n; j++) { for (size_t k = j + 1; k < n; k++) { double area = my::area(pos[i], pos[j], pos[k]); if (area < minVal) minVal = area; if (area > maxVal) maxVal = area; } } } cout << fixed << setprecision(1) << minVal << " " << fixed << setprecision(1) << maxVal << endl; } return 0; }