/** @JUDGE_ID: GOKURI_SQUEEZE ??? C++ */ #include #include #include #include #include #include #include #include #include using namespace std; #define FNAME "myacm.txt" #define cin fin const double DUMMY_MIN = -1.0; typedef complex dcomp; struct Point { dcomp v; string name; }; double area_with_const(const vector& points, int i, int j, int k) { dcomp ab = points[j].v - points[i].v; dcomp ac = points[k].v - points[i].v; double d = ab.real() * ac.imag() - ac.real() * ab.imag(); if (fabs(d) < 0.000001) { return DUMMY_MIN; } for (int l = 0; l < points.size(); ++l) { if (l == i || l == j || l == k) { continue; } dcomp pt = points[l].v - points[i].v; double s = (ac.imag() * pt.real() - ac.real() * pt.imag()) / d ; double t = (- ab.imag() * pt.real() + ab.real() * pt.imag()) / d; if (0 <= s && s <= 1.0 && 0 <= t && t <= 1.0 && s + t <= 1) { //cout << i << ' ' << j << ' ' << k << endl; return DUMMY_MIN; } } return fabs(d) / 2; } void solve(const vector& points, int N) { double area = DUMMY_MIN; int min_i, min_j, min_k; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { for (int k = j + 1; k < N; ++k) { double d; if ((d = area_with_const(points, i, j, k)) > area) { area = d; min_i = i; min_j = j; min_k = k; } } } } cout << points[min_i].name << points[min_j].name << points[min_k].name << endl; } int main() { ifstream fin(FNAME); if(!fin) return -1; int N; while (cin >> N, N) { vector points(N); for (int i = 0; i < N; ++i) { string str; double a, b; cin >> str >> a >> b; Point p; p.name = str; p.v = dcomp(a, b); points[i] = p; } solve(points, N); } return 0; }