## Solución al problema número 10112 de UVA - 10112.

Cualquier duda no dudes en contactar.

``````#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define PI acos(-1.0)
using namespace std;

struct point{
double x,y;
char c;
point(){x=y=0; c='\$';}
point(double _x,double _y, char _c){x=_x,y=_y, c=_c;}
};

struct vec { double x, y;  // name: `vec' is different from STL vector
vec(double _x, double _y) : x(_x), y(_y) {} };

vec toVec(point a, point b) {       // convert 2 points to vector a->b
return vec(b.x - a.x, b.y - a.y); }

double dot(vec a, vec b) { return (a.x * b.x + a.y * b.y); }

double norm_sq(vec v) { return v.x * v.x + v.y * v.y; }

double angle(point a, point o, point b) {  // returns angle aob in rad
vec oa = toVec(o, a), ob = toVec(o, b);
return acos(dot(oa, ob) / sqrt(norm_sq(oa) * norm_sq(ob))); }

double cross(vec a, vec b) { return a.x * b.y - a.y * b.x; }

// note: to accept collinear points, we have to change the `> 0'
// returns true if point r is on the left side of line pq
bool ccw(point p, point q, point r) {
return cross(toVec(p, q), toVec(p, r)) > 0; }

double cross(point o, point a, point b) {
return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
bool cmp(point a,point b){
return a.c<b.c;
}
bool inPolygon(point test, vector<point> g){
bool result = false;
for (unsigned i = 0, j = g.size() - 1; i < g.size(); j = i++) {
if ((g[i].y > test.y) != (g[j].y > test.y) &&
(test.x < (g[j].x - g[i].x) * (test.y - g[i].y) / (g[j].y-g[i].y) + g[i].x)) {
result = !result;
}
}
return result;
}
double area(vector<point> P) {
return abs(0.5 * (((P[2].y - P[0].y)*(P[1].x - P[0].x)) - ((P[1].y - P[0].y)*(P[2].x - P[0].x))));
}
// double area = Math.abs(0.5*(((tri.g[2].y-tri.g[0].y)(tri.g[1].x-tri.g[0].x))-((tri.g[1].y-tri.g[0].y)(tri.g[2].x-tri.g[0].x))));
int main()
{
int n;
while(scanf("%d",&n)==1 && n!=0)
{
vector<point> V;
vector<point> R;
double x,y;
char c;
for(int i=0; i<n;i++)
{
cin.ignore();
scanf("%c %lf %lf",&c,&x,&y);
V.push_back(point(x,y,c));
}
double areaR = -INF;
for(unsigned int i=0; i<V.size();i++)
for(unsigned int j=i+1; j<V.size();j++)
for(unsigned int k=j+1; k<V.size();k++)
{
vector<point> T; T.push_back(V[i]); T.push_back(V[j]); T.push_back(V[k]);
int flag=0;
for(unsigned int m=0; m<V.size() && flag==0;m++)
{
if(m==i || m==j || m==k) continue;
if(inPolygon(V[m],T)) flag=1;
}
if(flag==0) {
double res = area(T); if(res>areaR) { areaR=res; R=T; }
//printf("%c %c %c %lf %lf\n",T[0].c,T[1].c,T[2].c,areaR, res);
}
}
sort(R.begin(),R.end(),cmp);
for(auto v:R)
{
printf("%c",v.c);
}
printf("\n");
}
return 0;
}
``````

### No te pierdas nada.

Sigue en contacto con Isaac Lozano Osorio!