/******************************************* Problem - The Kings of Mesopotamia Solution By - Sean Falconer *******************************************/ #include #include #include #include using namespace std; struct Point { int x, y; char label; Point() {} int operator < (Point const & p) const { return label < p.label; } }; Point points[15]; int N; int tArea(Point & p1, Point & p2, Point & p3) { return abs((p3.y - p1.y) * (p2.x - p1.x) - (p2.y - p1.y) * (p3.x - p1.x)); } int isClear(int i, int j, int k, double area) { for(int p = 0; p < N; p++) if(p != i && p != j && p != k) { int a1 = tArea(points[p], points[i], points[j]); a1 += tArea(points[p], points[i], points[k]); a1 += tArea(points[p], points[k], points[j]); if(a1 == area) return 0; } return 1; } int main() { int i; while(cin >> N) { if(!N) break; for(i = 0; i < N; i++) cin >> points[i].label >> points[i].x >> points[i].y; Point triangle[3]; int area = INT_MIN; for(i = 0; i < N; i++) { for(int j = i+1; j < N; j++) { for(int k = j+1; k < N; k++) { int a = tArea(points[i], points[j], points[k]); if(a > area && isClear(i, j, k, a)) { area = a; triangle[0] = points[i]; triangle[1] = points[j]; triangle[2] = points[k]; } } } } sort(triangle, triangle+3); cout << setiosflags(ios::fixed) << setprecision(2); for(i = 0; i < 3; i++) cout << triangle[i].label; cout << " " << (double)area*0.5 << endl; } return 0; }