這是一個幾何題。題意是給出一系列點，點最多才15個，求一個這里面的三個點組合出來的三角形，其面積是最大的，而且沒有任何其它
的點在這個三角形的內(nèi)部和邊界上。求三角形的面積，題目上面已經(jīng)給了公式，也可以用0.5*|a|*|b|*sin(a,b)求，這里的a和b指的是2條
邊代表的向量。
現(xiàn)在就剩下一個問題了，怎么判斷一個點在三角形的內(nèi)部和邊界上。在邊界上，比較好判斷，判斷是否共線，然后再點是在線段的內(nèi)部。
具體說明下，判斷一個點在三角形內(nèi)部的思路。我用的還是線性規(guī)劃的思想。
如果該點在三角形的內(nèi)部，那么任取三角形的一條邊，
該內(nèi)部點和剩余的三角形的一個頂點必定在三角形的那條的邊的同一側(cè)。這個方法也可以推廣到N邊的凸多邊形，證明的話很簡單，
因為線性規(guī)劃一直在劃分區(qū)域。所以，劃分到最后圍起來的區(qū)域就是凸多邊形的內(nèi)部了。
至于寫代碼的話，由于是第一次寫這種幾何題，寫得很凌亂。
代碼如下：
#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)的同一側(cè)(不能在直線上)
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的坐標(biāo)代入直線方程計算結(jié)果，然后將結(jié)果相乘
//乘積必須大于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的同一側(cè)\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)的外側(cè)也會判斷為假
//所以需要先在上面判斷點是否在邊的內(nèi)側(cè)
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)部\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;
}