HDU 4709 Herding 幾何題解

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;
}