HDU 4709 Herding 几何题解
求全部点组成的三角形最小的面积，0除外。
本题就枚举全部能够组成的三角形，然后保存最小的就是答案了。由于数据量非常少。
复习一下怎样求三角形面积。最简便的方法就是向量叉乘的知识了。
并且是二维向量叉乘P1(ax, ay), P2(bx, by)。公式为：|P1 X P2| = abs(ax*by - ay*bx)
三角形面积就是|P1 X P2| / 2;
本题也是float过不了。换成double就能够过了。
const int MAX_N = 101;
struct VertexPoint
{
double x, y;
float crossProduct(const VertexPoint &n) const
{
return x * n.y - y * n.x; //cross product
}
VertexPoint operator-(const VertexPoint &n) const
{
VertexPoint a;
a.x = x - n.x;
a.y = y - n.y;
return a;
}
};
int N;
VertexPoint P[MAX_N];
int main()
{
int T;
VertexPoint a, b;
scanf("%d", &T);
while (T--)
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
scanf("%lf %lf", &P[i].x, &P[i].y);
}
double area = DBL_MAX;
for (int i = 0; i < N; i++)
{
for (int j = i+1; j < N; j++)
{
for (int k = j+1; k < N; k++)
{
a = P[j] - P[i];
b = P[k] - P[i];
double tmp = fabs(a.crossProduct(b) * 0.5);
if (tmp > DBL_EPSILON) area = min(area, tmp);
}
}
}
if (area == DBL_MAX) puts("Impossible");
else printf("%.2lf\n", area);
}
return 0;
}本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5150660.html，如需转载请自行联系原作者