设为首页 加入收藏

TOP

HDU 4709 Herding 几何题解
2015-07-20 17:54:27 来源: 作者: 【 】 浏览:1
Tags: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;
}



】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇Hdu4952 - Number Transformation.. 下一篇HDU 4772 Zhuge Liang's Pass..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: