// Maximum-TNT #include #include #include #include #include #include #include #include #include #include using namespace std; typedef complex cmp_t; #define im imag() #define re real() #define cin fin ifstream fin("myacm.txt"); const int BUFSIZE = 1024; const int INF=999999; struct vertics { char id; cmp_t loc; vertics(){} }; bool idless(vertics a, vertics b) { return a.id < b.id; } vector g_vert; double g_area_max; vector g_path; bool Input() { int n; cin >> n; if(n == 0) return false; g_vert.assign(n, vertics()); for(int i=0;i> g_vert[i].id; double x, y; cin >> x >> y; g_vert[i].loc = cmp_t(x, y); } sort(g_vert.begin(), g_vert.end(), idless); return true; } double Gaiseki(cmp_t a, cmp_t b) { return a.re * b.im - a.im * b.re; } bool Reless(cmp_t a, cmp_t b) { if(a.re < b.re) return true; else if(a.re > b.re) return false; else return a.im < b.im; } bool isOnline(cmp_t p, cmp_t a, cmp_t b) { // cout << a << " " << p << " " << b << endl; cmp_t tmp[3] = {a, p, b}; sort(tmp, tmp + 3, Reless); // cout << "s" << tmp[0] << " " << tmp[1] << " " << tmp[2] << endl; return tmp[1] == p; } bool InsideTriangle(cmp_t p, vector &data) { int sign = 0; for(int i=1;i<(int)data.size();i++) { double tmp = Gaiseki(data[i] - p, data[i-1] - p); if(tmp == 0) { if(isOnline(p, data[i],data[i-1])) return true; else return false; } else if(sign == 0) { if(tmp > 0) sign = 1; else if(tmp < 0) sign = -1; } else { if(tmp > 0 && sign == -1) return false; else if(tmp < 0 && sign == 1) return false; } } return true; } double GetArea(vector &data) { double ans = 0; cmp_t v1, v2(data[1] - data[0]); for(int i=1;i<(int)data.size(); i++) { v1 = v2; v2 = data[i+1] - data[0]; ans += Gaiseki(v1,v2); } return abs(ans / 2.0); } void UpdateMaxArea(vector &path) { int n = g_vert.size(); vector triangle(4); for(int i=0;i<3;i++) triangle[i] = g_vert[path[i]].loc; triangle[3] = g_vert[path[0]].loc; for(int i=0;i g_area_max) { g_path = path; g_area_max = area; } } void Solve(int depth, int first, vector &path) { int n = g_vert.size(); if(depth == 3) { UpdateMaxArea(path); return; } for(int i=first; i path(3); Solve(0, 0, path); Output(); } }