這是一個幾何題。題意是給出一系列點，點最多才15個，求一個這里面的三個點組合出來的三角形，其面積是最大的，而且沒有任何其它
的點在這個三角形的內部和邊界上。求三角形的面積，題目上面已經給了公式，也可以用0.5*|a|*|b|*sin(a,b)求，這里的a和b指的是2條
邊代表的向量。
現在就剩下一個問題了，怎么判斷一個點在三角形的內部和邊界上。在邊界上，比較好判斷，判斷是否共線，然后再點是在線段的內部。
具體說明下，判斷一個點在三角形內部的思路。我用的還是線性規劃的思想。
如果該點在三角形的內部，那么任取三角形的一條邊，
該內部點和剩余的三角形的一個頂點必定在三角形的那條的邊的同一側。這個方法也可以推廣到N邊的凸多邊形，證明的話很簡單，
因為線性規劃一直在劃分區域。所以，劃分到最后圍起來的區域就是凸多邊形的內部了。
至于寫代碼的話，由于是第一次寫這種幾何題，寫得很凌亂。
代碼如下：
#include <stdio.h>
#include <math.h>
#define MAX (20)
int nN;
struct Point
{
char szLabel[5];
int x;
int y;
};
Point points[MAX];
//三點是否共線
bool IsOneLine(int nOne, int nTwo, int nThree)
{
int nA = points[nTwo].x - points[nOne].x;
int nB = points[nTwo].y - points[nOne].y;
int nC = points[nThree].x - points[nOne].x;
int nD = points[nThree].y - points[nOne].y;
return (nA * nD == nB * nC);
}
//點nOne和點nTwo是否在直線(nBeg,nEnd)的同一側(不能在直線上)
bool IsSameSide(int nBeg, int nEnd, int nOne, int nTwo)
{
//求直線的向量
int nA = points[nBeg].x - points[nEnd].x;
int nB = points[nBeg].y - points[nEnd].y;
//直線方程為nB(x - points[nBeg].x) - nA(y - points[nBeg].y) = 0
//分別用nOne和nTwo的坐標代入直線方程計算結果，然后將結果相乘
//乘積必須大于0
int nRes = (nB * (points[nOne].x - points[nBeg].x) - nA * (points[nOne].y - points[nBeg].y))
* (nB * (points[nTwo].x - points[nBeg].x) - nA * (points[nTwo].y - points[nBeg].y));
if (nRes > 0)
{
//printf("點:%d,點:%d,在直線nBeg:%d, nEnd:%d的同一側\n", nOne, nTwo, nBeg, nEnd);
}
return nRes > 0;
}
//點是否在三角形(nOne, nTwo, nThree)外部
bool PointOutTriangle(int nOne, int nTwo, int nThree, int nPoint)
{
//前面3個ifelse是判斷點是否在邊上
if (IsOneLine(nOne, nTwo, nPoint))
{
if ((points[nOne].x - points[nPoint].x) * (points[nTwo].x - points[nPoint].x) <= 0)
{
return false;
}
}
else if (IsOneLine(nOne, nThree, nPoint))
{
if ((points[nOne].x - points[nPoint].x) * (points[nThree].x - points[nPoint].x) <= 0)
{
return false;
}
}
else if (IsOneLine(nTwo, nThree, nPoint))
{
if ((points[nTwo].x - points[nPoint].x) * (points[nThree].x - points[nPoint].x) <= 0)
{
return false;
}
}
//下面的IsSameSide如果nPoint在直線的(nOne,nTwo)的外側也會判斷為假
//所以需要先在上面判斷點是否在邊的內側
return !(IsSameSide(nOne, nTwo, nThree, nPoint)
&& IsSameSide(nOne, nThree, nTwo, nPoint)
&& IsSameSide(nTwo, nThree, nOne, nPoint));
}
bool IsValid(int nOne, int nTwo, int nThree)
{
if (IsOneLine(nOne, nTwo, nThree))
{
//printf("點:%d,%d,%d共線\n", nOne, nTwo, nThree);
return false;
}
for (int i = 0; i < nN; ++i)
{
if (i == nOne || i == nTwo || i == nThree)
{
continue;
}
if (!PointOutTriangle(nOne, nTwo, nThree, i))
{
//printf("點:%d, 在三角形:%d,%d,%d內部\n", i, nOne, nTwo, nThree);
return false;
}
}
return true;
}
//計算三角形(nOne, nTwo, nThree)的面積
double GetArea(int nOne, int nTwo, int nThree)
{
return 0.5 * fabs((points[nThree].y - points[nOne].y) * (points[nTwo].x - points[nOne].x)
- (points[nTwo].y - points[nOne].y) * (points[nThree].x - points[nOne].x));
}
int main()
{
while (scanf("%d", &nN), nN)
{
for (int i = 0; i < nN; ++i)
{
scanf("%s%d%d", points[i].szLabel, &points[i].x, &points[i].y);
}
double fMaxArea = 0.0;
int nI = -1, nJ = -1, nK = -1;
for (int i = 0; i < nN - 2; ++i)
{
for (int j = i + 1; j < nN - 1; ++j)
{
for (int k = j + 1; k < nN; ++k)
{
if (IsValid(i, j, k))
{
//printf("i:%d,j:%d,k:%d valid\n", i, j, k);
double fArea = GetArea(i, j, k);
//printf("Area:%f\n", fArea);
if (fArea > fMaxArea)
{
nI = i;
nJ = j;
nK = k;
fMaxArea = fArea;
}
}
}
}
}
printf("%s%s%s\n", points[nI].szLabel, points[nJ].szLabel, points[nK].szLabel);
}
return 0;
}