Q10112: Myacm Triangles

/*
   判斷是否在三角形內，我用面積的和的方法來看
   如果大於表示在外面，等於就是在裡面或線上
   fabs(total-t_area) < 1e-6 因為double 會有誤差

   Run time: 0.000
*/
#include <stdio.h>
#include <math.h>

typedef struct {
   int x, y;
   char ch;
} Pos;
Pos pos[15];

double t_area;
double max;

// calculate the triangle area
double triangle(Pos a, Pos b, Pos c);

// 因為輸出必須按照字母順序
void sort(char a, char b, char c);
void swap(int &a, int &b);

int main()
{
   int n;
   int i, j, k;
   int l;
   int index_a, index_b, index_c;

   double area_a, area_b, area_c;
   double total;

   while (scanf("%d", &n))
   {
       if (!n) break;

       getchar();

       for ( i = 0; i < n-1; i++)
           scanf("%c%d%d\n", &pos[i].ch, &pos[i].x, &pos[i].y);
       scanf("%c%d%d", &pos[i].ch, &pos[i].x, &pos[i].y);

       max = 0;

       for ( i = 0; i < n; i++)
       {
           for ( j = i+1; j < n; j++)
           {
               for ( k = j+1; k < n; k++)
               {
                   // calculate the triangle area
                   t_area = triangle(pos[i], pos[j], pos[k]);

                   if (t_area > max)
                   for ( l = 0; l < n; l++)
                   {
                       if (l == i || l == j || l == k) continue;

                       area_a = triangle(pos[i], pos[j], pos[l]);
                       area_b = triangle(pos[i], pos[l], pos[k]);
                       area_c = triangle(pos[l], pos[j], pos[k]);

                       total = area_a+area_b+area_c;

                       if (fabs(total-t_area) < 1e-6)
                           break;
                   }

                   if (l == n && max < t_area)
                   {
                       index_a = i;
                       index_b = j;
                       index_c = k;
                       max = t_area;
                   }
               }
           }
       }

       sort(pos[index_a].ch, pos[index_b].ch, pos[index_c].ch);

   }

   return 0;
}

double triangle(Pos a, Pos b, Pos c)
{
   double area;
   area = a.x*b.y+b.x*c.y+c.x*a.y-(b.x*a.y+c.x*b.y+a.x*c.y);
   area = area >= 0 ? area : -area;

   return 0.5*area;
}

void sort(char a, char b, char c)
{
   int i, j;
   int index;
   int arr[3];
   int n = 3;
   arr[0] = a;
   arr[1] = b;
   arr[2] = c;

   int max;
   for ( i = 0; i < n-1; i++)
   {
       max = arr[0];
       index = 0;
       for ( j = 0; j < n-i; j++)
       {
           if (arr[j] > max)
           {
               max = arr[j];
               index = j;
           }
       }
       swap(arr[index], arr[j-1]);
   }

   for ( i = 0; i < n; i++)
       printf("%c", arr[i]);
   printf("\n");
}

void swap(int &a, int &b)
{
   int tmp;
   tmp = a;
   a = b;
   b = tmp;
}