1 条题解
-
0
#include <iostream> #include <cmath> #include <vector> #include <cstdlib> using namespace std; struct Point { char label; int x, y; }; double area(const Point& a, const Point& b, const Point& c) { return fabs((double)(b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) / 2.0; } bool is_inside(const Point& p, const Point& a, const Point& b, const Point& c) { double A = area(a, b, c); double A1 = area(p, b, c); double A2 = area(a, p, c); double A3 = area(a, b, p); return fabs((A1 + A2 + A3) - A) < 1e-6; } bool contains_other(const Point& a, const Point& b, const Point& c, const vector<Point>& points) { for (int i = 0; i < points.size(); ++i) { Point p = points[i]; if (p.label == a.label || p.label == b.label || p.label == c.label) continue; if (is_inside(p, a, b, c)) return true; } return false; } int main() { int n; while (cin >> n && n != 0) { vector<Point> points(n); for (int i = 0; i < n; ++i) { cin >> points[i].label >> points[i].x >> points[i].y; } double max_area = -1; string best_triangle = ""; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) for (int k = j + 1; k < n; ++k) { Point a = points[i], b = points[j], c = points[k]; if (contains_other(a, b, c, points)) continue; double ar = area(a, b, c); if (ar > max_area) { max_area = ar; char labels[3] = { a.label, b.label, c.label }; for (int x = 0; x < 2; ++x) for (int y = x + 1; y < 3; ++y) if (labels[x] > labels[y]) { char temp = labels[x]; labels[x] = labels[y]; labels[y] = temp; } best_triangle = string() + labels[0] + labels[1] + labels[2]; } } cout << best_triangle << endl; } return 0; }
- 1
信息
- ID
- 570
- 时间
- 1000ms
- 内存
- 10MiB
- 难度
- 7
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者