Problem B: Myacm Triangles

There has been considerable archeological work on the ancient Myacm culture. Many artifacts have been found in what have been called power fields: a fairly small area, less than 100 meters square where there are
from four to fifteen tall monuments with crystals on top. Such an area is mapped out above. Most of the artifacts discovered have come from inside a triangular area between just three of the monuments, now called the power triangle. After considerable analysis
archeologists agree how this triangle is selected from all the triangles with three monuments as vertices: it is the triangle with the largest possible area that does not contain any other monuments inside the triangle or on an edge of the triangle. Each field
contains only one such triangle.

Archeological teams are continuing to find more power fields. They would like to automate the task of locating the power triangles in power fields. Write a program that takes the positions of the monuments in any
number of power fields as input and determines the power triangle for each power field.

A useful formula: the area of a triangle with vertices (x₁, y₁), (x₂, y₂), and (x₃, y₃) is
the absolute value of

0.5 × [(y₃ - y₁)(x₂ - x₁) - (y₂ - y₁)(x₃ - x₁)].

For each power field there are several lines of data. The first line is the number of monuments: at least 4, and at most 15. For each monument there is a data line that starts with a one character label for the
monument and is followed by the coordinates of the monument, which are nonnegative integers less than 100. The first label is A, and the next is B, and so on.

There is at least one such power field described. The end of input is indicated by a 0 for the number of monuments. The first sample data below corresponds to the diagram in the problem.

For each power field there is one line of output. It contains the three labels of the vertices of the power triangle, listed in increasing alphabetical order, with no spaces.

Example input:

6
A 1 0
B 4 0
C 0 3
D 1 3
E 4 4
F 0 6
4
A 0 0
B 1 0
C 99 0
D 99 99
0

Example output:

BEF
BCD

题意：有n个点，每三个点可以构成一个三角形。而当一个三角形中，包括边界不包括其他点时，为符合要求的三角形。求出所有符合条件的三角形当中面积最大的一个，保证只有一个，并且按照字典顺序输出该三角形的三个顶点。

首先，题目中给的公式做出一个解释。其实就是按照叉×的定义，三角形面积之和为a×b/2=|a|×|b|*sinA/2

还有就是判断点是否在三角形内，我没有想出特别好的方法。也还没有开始看几何。所以就采用了面积法

如果点在三角形内，包括边界的话。那么该点与另外三点中的任意两点组成的三角形之和应该等于该三角形。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x[20],y[20];
double area(int i, int j, int k)
{
    double s;
    s=0.5*((y[k]-y[i])*(x[j]-x[i])-(y[j]-y[i])*(x[k]-x[i]));
    return fabs(s);
}
int main ()
{
    int t,i,j,k,A,B,C,r;
    double S=0,s;
    char ch;
    while(cin>>t)
    {
        S=0;
        if (t==0) break;
        for (i=1; i<=t; i++)
            cin>>ch>>x[i]>>y[i];
        for (i=1; i<=t-2; i++)
            for (j=i+1; j<=t-1; j++)
                for (k=j+1; k<=t; k++)
                {
                    s=area(i,j,k);
                    if (s>S)
                    {
                        bool flag=true;
                        for (r=1; r<=t; r++)
                            if (r!=k && r!=i && r!=j)
                            {
                                if (s==area(i,j,r)+area(i,k,r)+area(j,k,r))
                                {
                                    flag=false;
                                    break;
                                }
                            }
                        if (flag)
                        {
                            S=s;
                            A=i;
                            B=j;
                            C=k;
                        }
                    }
                }
        printf("%c%c%c\n",A+64,B+64,C+64);
    }
    return 0;
}