ZOJ 1010 Area

1010 面积

原题目链接

中学生杰瑞沉迷于数学研究。也许他所思考的问题对于专家来说实在是太简单了。但作为一个业余爱好者，尤其是15岁的男孩，他已经做得很好了。他如此沉迷于数学问题思考，以至于他很容易用数学方法解决他遇到的每一个问题。一天，他在课桌上发现了一张纸。他妹妹玛丽，一个四岁的小女孩，在上面画了一些线。但这些线却意外地形成了一种特殊的凹多边形，如图1所示。
在这里插入图片描述

“太棒了！”他想，“这个多边形看起来太规则了。我刚刚学会了如何计算三角形、矩形和圆形的面积。我肯定能找到如何计算这个图形面积的方法。”于是他就这么做了。首先，他用坐标标记了多边形中的顶点，如图 2 所示。然后他毫不费力地找到了结果——0.75。
在这里插入图片描述

当然，他并不满足于能解答这么简单的问题。他自问：“嗯，如果纸上有一个随机多边形，那么我该如何计算面积呢？”到目前为止，他还没有找到计算随机多边形面积的一般规则。他很清楚，这个问题的答案超出了他的能力范围。所以他请你，一位博学的专家，为他提供帮助。这种善意的行为将受到他的高度赞赏。

输入

输入数据由多个图形组成。每个图形的输入的第一行包含一个整数 n，即图形中的顶点数。（0 <= n <= 1000）。

接下来的 n 行，每行包含一对实数，描述顶点的坐标 (xi, yi)。每个测试用例中的图形从第一个顶点开始到第二个顶点，然后从第二个顶点到第三个顶点，依此类推。最后，它从第 n 个顶点闭合到第一个顶点。

输入以空图形（n = 0）结束。并且该图形不被处理。

输出

如下所示，每个图形的输出应包含图形编号和冒号，后跟图形的面积或字符串“Impossible”。

如果图形是多边形，则计算其面积（精确到小数点后两位）。根据输入的顶点，如果它们不能组成多边形（即一条线与另一条不应该与之相连的线相交，例如，在有四条线的图形中，第一条线与第三条线相交），则显示“Impossible”，表示该图形不能是多边形。如果顶点数量不足以组成一个封闭的多边形，则输出信息也应该是“Impossible”。

在每个测试用例之间打印一个空白行。

示例输入

样本输入的输出

Figure 1: 0.75
Figure 2: Impossible

c++代码

#include<bits/stdc++.h>
#include<stdio.h>using namespace std;//计算向量(x1, y1)与向量(x2, y2)的叉乘结果
double cross_product(double x1, double y1, double x2, double y2) {return x1 * y2 - y1 * x2;
}//判断四个不同的顶点构成的线段是否相交于某一点
//返回true表示相交,false表示不相交
//利用叉乘结果去判断是否相交,数学证明我就不说了，可以去搜相关文章
bool isintersect(vector<pair<double, double>> nodes) {double cross1 = cross_product(nodes[1].first - nodes[0].first, nodes[1].second - nodes[0].second, nodes[2].first - nodes[0].first, nodes[2].second - nodes[0].second);double cross2 = cross_product(nodes[1].first - nodes[0].first, nodes[1].second - nodes[0].second, nodes[3].first - nodes[0].first, nodes[3].second - nodes[0].second);double cross3 = cross_product(nodes[3].first - nodes[2].first, nodes[3].second - nodes[2].second, nodes[0].first - nodes[2].first, nodes[0].second - nodes[2].second);double cross4 = cross_product(nodes[3].first - nodes[2].first, nodes[3].second - nodes[2].second, nodes[1].first - nodes[2].first, nodes[1].second - nodes[2].second);if (cross1 == 0 && cross2 == 0 && cross3 == 0 && cross4 == 0){if (nodes[1].second < nodes[2].second || nodes[3].second < nodes[0].second) return false;}//单独考虑四点共线不相交的特殊情况else if (cross1 * cross2 <= 0 && cross3 * cross4 <= 0) return true;else return false;
}//判断图形是否存在面积
//返回true存在面积,返回false，不存在面积
//思路是，每一条线与它不相邻的线去对比是否相交，相交则不存在面积
bool check(vector<pair<double, double>> nodes) {int n = nodes.size();vector<pair<double, double>> middle;for (int i = 3; i < n; i++) {middle.push_back(nodes[i - 1]);middle.push_back(nodes[i]);for (int j = 0; j < i - 2; j++) {middle.push_back(nodes[j]);middle.push_back(nodes[j + 1]);if (isintersect(middle)) return false;middle.pop_back();middle.pop_back();}middle.pop_back();middle.pop_back();}middle.push_back(nodes[0]);//特殊处理最后一根线，也就是第一个顶点和最后一个顶点的线middle.push_back(nodes[n - 1]);for (int j = 1; j < n - 2; j++) {middle.push_back(nodes[j]);middle.push_back(nodes[j + 1]);if (isintersect(middle)) return false;middle.pop_back();middle.pop_back();}return true;
}//分割成若干个三角形，采用叉乘法矢量累加，计算图形的面积
double getarea(vector<pair<double, double>> nodes){int n = nodes.size();double sum = 0;for (int i = 1; i < n - 1; i++){double x1 = nodes[i].first - nodes[0].first;double y1 = nodes[i].second - nodes[0].second;double x2 = nodes[i + 1].first - nodes[0].first;double y2 = nodes[i + 1].second - nodes[0].second;sum += cross_product(x1, y1, x2, y2);}return fabs(sum) / 2;
}int main() {int n, count = 0;while (cin >> n) {if (n == 0) break;count++;vector<pair<double, double>> nodes(n);for (int i = 0; i < n; i++) {cin >> nodes[i].first >> nodes[i].second;}cout << "Figure " << count << ": ";if (n < 3 || !check(nodes)) cout << "Impossible" << endl;else printf("%.2lf\n", getarea(nodes));}return 0;
}//by wqs

题目背景与需求梳理

题目要求我们计算一些不规则多边形的面积，输入是多边形的顶点坐标，要求我们计算并输出每个多边形的面积。如果该多边形不合法（如自交、多条线段相交），则输出“Impossible”。当多边形的顶点数量小于3时，也应该输出“Impossible”。

输入：
- 多组图形，每组图形的顶点数为 n，接下来为 n 个二维坐标。
- 输入以 n = 0 结束，表示输入结束。
输出：
- 每个图形的编号和面积，若图形不合法则输出“Impossible”。

题目思路

为了正确地求解这个问题，我们可以按以下步骤逐步分析和实现：

输入处理：
- 每组图形的顶点数 n（顶点坐标通过坐标对的形式给出），直到 n = 0。
合法性判断：
- 若顶点数 n < 3，图形无法形成封闭多边形，直接输出“Impossible”。
- 需要判断多边形是否是合法的，不合法的多边形为有自交（某些边相交）或顶点数量不足。
- 可以通过判断任意两条不相邻边是否相交来验证图形的合法性。
计算面积：
- 使用 多边形面积公式（也称为 叉积法）来计算多边形的面积。对于一个简单的多边形，面积可以通过顶点坐标按顺时针或逆时针计算：