首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。