UVa 10112 Myacm三角形

/*

* 解题思路：

* 求最大的一个三角形、且其中不包含任一顶点,参考P84

*/

#include <math.h>
#include <stdio.h>
char s[ 105 ],c;
int mon[ 105 ][ 2 ];
double area( double x1,double y1,double x2,double y2,double x3,double y3 )
{ return fabs(0.5*((y3-y1)*(x2-x1)-(y2-y1)*(x3-x1))); }
int main( )
{
    int n;
    int i,j,k,l;
    int x,y,z,maxA,flag;
    double areaX,areaA,area1,area2,area3;

    while( scanf("%d",&n) && n )
    {
        for( i=0;i<n;i++ )
        {
            getchar();
            scanf("%c%d%d",&c,&mon[ i ][ 0 ],&mon[ i ][ 1 ] );
        }
        areaA = 0;
        for( i=0;i<n;i++ )
            for( j=i+1;j<n;j++ )
                for( k=j+1;k<n;k++ )
                {  
                    flag = 1;
                    areaX = area(mon[i][0],mon[i][1],mon[j][0],mon[j][1],mon[k][0],mon[k][1]);
                    for( l=0;l<n;l++ )
                        if( l!=i && l!= j && l!= k )
                        {
                            area1 = area(mon[i][0],mon[i][1],mon[j][0],mon[j][1],mon[l][0],mon[l][1]);
                            area2 = area(mon[i][0],mon[i][1],mon[l][0],mon[l][1],mon[k][0],mon[k][1]);
                            area3 = area(mon[l][0],mon[l][1],mon[j][0],mon[j][1],mon[k][0],mon[k][1]);
                            if( areaX - area1 - area2 - area3 >= 0 ) 
                            {
                                flag = 0;
                                break;
                            }
                        } 
                    if( flag && areaX > areaA ){ areaA = areaX , x = i , y = j , z = k; }
                }
        printf("%c%c%c\n",(char)(x+65),(char)(y+65),(char)(z+65));
    }
    return 0;
}

UVa 10112 Myacm三角形

原文：http://blog.csdn.net/u011886588/article/details/19847683