UVa第一卷最后一题。

求内部不含点并且面积最大的三角形。

暴力。

代码如下：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5  6 using namespace std; 7  8 typedef struct node 9 {10     char ch;11     int x, y;12 }node;13 14 node dot[20];15 16 double mianji(int i, int j, int k)　　　　//求三角形的面积17 {18     return fabs(0.5*((dot[k].y-dot[i].y)*(dot[j].x-dot[i].x)-(dot[j].y-dot[i].y)*(dot[k].x-dot[i].x)));19 }20 21 int judge(int i, int j, int k, int l)　　　　//判断点是否在三角形之内22 {23     if (mianji(i,j,k)>=mianji(j,k,l)+mianji(i,k,l)+mianji(i, j, l))24         return 1;25     return 0;26 }27 28 int main()29 {30     int n, i, j, k, l;31     char s[3];32     while(cin >> n, n)33     {34         memset(s, 0, sizeof(s));35         for (i=1; i<=n; i++)36             cin >> dot[i].ch >> dot[i].x >> dot[i].y;37         double maxs=0;38         for (i=1; i<=n-2; i++)39         {40             for (j=i+1; j<=n-1; j++)41             {42                 for (k=j+1; k<=n; k++)43                 {44                     int flag=0;45                     for (l=1; l<=n; l++)46                     {47                         if (l == i || l == j || l == k)48                             continue;49                         if (judge(i, j, k, l))50                         {51                             flag=1;52                             break;53                         }54                     }55                     double t=mianji(i, j, k);56                     if (flag == 0 && maxs < t)57                     {58                         maxs=t;59                         s[0]=dot[i].ch;60                         s[1]=dot[j].ch;61                         s[2]=dot[k].ch;62                     }63                 }64             }65         }66         cout << s[0] << s[1] << s[2] << endl;67     }68     return 0;69 }