#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#define LOCALtypedefstructPoint{
charlabel;
intx;
inty;
}point;
pointPoints[20];
intsearch[500][3];
intc;
inttemp[3];
intvisited[30];
voiddfs(intpos, intn);
doublearea(pointa, pointb, pointc);
intinside_triangle(pointa, pointb, pointc, pointd);
intcross(pointa, pointb, pointc);
intmain()
{
inttests;
inti, j;
pointtriangle[3];
intnodeVis[20];
doubles ;
intok;
doubletemp;
charans[3];
#ifdef LOCALfreopen("c://uva_in.txt", "r", stdin);
#endifwhile (scanf("%d", &tests) &&tests!=0)
{
c=0;
s=-1.0;
memset(visited, 0, sizeof(visited));
dfs(0, tests);
fgetc(stdin);
for (i=1; i<=tests; i++)
{
scanf("%c%d%d", &(Points[i].label), &(Points[i].x), &(Points[i].y));
fgetc(stdin);
}
for (i=0; i<c; i++)
{
memset(nodeVis, 0, sizeof(nodeVis));
for (j=0; j<3; j++)
{
nodeVis[search[i][j]] =1;
triangle[j].label=Points[search[i][j]].label;
triangle[j].x=Points[search[i][j]].x;
triangle[j].y=Points[search[i][j]].y;
}
ok=1;
for (j=1; j<=tests; j++)
{
if (!nodeVis[j])
{
if (inside_triangle(triangle[0], triangle[1], triangle[2], Points[j]))
{
ok=0;
break;
}
}
}
temp=area(triangle[0], triangle[1], triangle[2]);
if (ok&& (temp>s))
{
s=temp;
ans[0] =triangle[0].label;
ans[1] =triangle[1].label;
ans[2] =triangle[2].label;
}
}
for (i=0; i<3; i++)
printf("%c", ans[i]);
printf("/n");
}
return0;
}
voiddfs(intpos, intn)
{
inti;
if (pos==3)
{
search[c][0] =temp[0];
search[c][1] =temp[1];
search[c][2] =temp[2];
c++;
} else {
for (i=1; i<=n; i++)
{
if (!visited[i] && (i>temp[pos-1]))
{
visited[i] =1;
temp[pos] =i;
dfs(pos+1, n);
visited[i] =0;
}
}
}
}
doublearea(pointa, pointb, pointc)
{
intx1, y1, x2, y2;
doubles;
x1=b.x-a.x;
y1=b.y-a.y;
x2=c.x-a.x;
y2=c.y-a.y;
s=fabs(x1*y2-y1*x2) /2.0;
returns;
}
intinside_triangle(pointa, pointb, pointc, pointd)
{
if ((cross(a, b, d) >=0&&cross(b, c, d) >=0&&cross(c, a, d) >=0) || (cross(a, b, d) <=0&&cross(b, c, d) <=0&&cross(c, a, d) <=0))
return1;
elsereturn0;
}
intcross(pointa, pointb, pointc)
{
intx1, y1, x2, y2;
inttemp;
x1=b.x-a.x;
y1=b.y-a.y;
x2=c.x-a.x;
y2=c.y-a.y;
temp=x1*y2-x2*y1;
returntemp;
}