计算几何(欧拉定理) - That Nice Euler Circuit - UVA 1342

计算几何(欧拉定理) - That Nice Euler Circuit - UVA 1342

题意：

$按{照}^{\prime \prime }一笔{画}^{\prime \prime }的顺序，给出欧拉回路的n个点，$

$计算这个欧拉回路所有的线段将平面分成了几部分。$

输入：

$多组测试数据，$

$首行包括一个正整数n，表示点的数量(起点和终点相同)$

输出：

$平面的数量。$

Sample Input

5 0 0 0 1 1 1 1 0 0 0 7 1 1 1 5 2 1 2 5 5 1 3 5 1 1 0

Sample Output

Case 1: There are 2 pieces. Case 2: There are 5 pieces.

数据范围：

$4\le n\le 300$

---

分析：

欧拉定理：$如果一个联通平面图G有个u顶点、e条边、f个面，那么$

$$v-e+f=2$$

$本题要求平面的数量f=e-v+2$

$我们若能计算出整个图中边的数量e和点的数量v，就能够得到f。$

$初始状态时给定我们n个点(实际上是n-1个点)构成的欧拉回路，那么v=n-1，e=n-1,$

$因为各边之间可能会产生交点，且存在三点共线的情况(此时一条边被分成两条边)，$

$故我们要统计新增加的点的数量，以及新生成的边的数量。$

$①、先求出任意两点连线的交点，然后将所有点排序后去重，得到的点的数量即v。$

$$\begin{gathered} ②、判断所有新生成的点是否在初始图中的某条线段上， \\ 即判断新生成的点与原先任意某两点是否严格的三点共线。若存在这样的情况，e++。 \end{gathered}$$

注意：

$求直线交点时，要先判断两直线是否相交。$

代码：

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <fstream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; const double eps = 1e-10; const double pi = acos(-1.0); struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} }; int dcmp(double x) { if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } //点与向量 typedef Point Vector; Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } Vector operator - (Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); } Vector operator * (Vector A, double p) { return Vector(A.x * p, A.y * p); } Vector operator / (Vector A, double p) { return Vector(A.x / p, A.y / p); } bool operator < (const Point& a, const Point& b) { return a.x < b.x || (!dcmp(a.x - b.x) && a.y < b.y); } bool operator == (const Point& a, const Point& b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; } double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; } double Length(Vector A) { return sqrt(Dot(A, A)); } double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); } //A和B夹角 double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; } //若A到B逆时针则为正，否则为负 double Area2(Point A, Point B, Point C) { return Cross(B - A, C - A); } //三角形ABC的面积的两倍(有方向) double angle(Vector v) { return atan2(v.y, v.x); } //arctan(y/x) double dis2(Point A, Point B) { return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y); } Vector Rotate(Vector A, double rad) //向量A逆时针旋转rad度 { return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad)); } Point GetLineIntersection(Point P, Vector v, Point Q, Vector w) //求过点P的向量v方向上的直线与过点Q的向量w上的直线的交点 { Vector u = P - Q; double t = Cross(w, u) / Cross(v, w); return P + v * t; } bool OnSegment(Point p, Point a1, Point a2) //判断点p是否在线段a1a2上 { return dcmp(Cross(a1 - p, a2 - p)) == 0 && dcmp(Dot(a1 - p, a2 - p)) < 0; } bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2) { double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1); double c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1); //if判断控制是否允许线段在端点处相交，根据需要添加 /*if (!dcmp(c1) || !dcmp(c2) || !dcmp(c3) || !dcmp(c4)) { bool f1 = OnSegment(b1, a1, a2); bool f2 = OnSegment(b2, a1, a2); bool f3 = OnSegment(a1, b1, b2); bool f4 = OnSegment(a2, b1, b2); bool f = (f1 | f2 | f3 | f4); return f; }*/ return (dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0); } const int N = 310; int n; Point V[N*N]; Point P[N]; int main() { int T = 1; while (scanf("%d", &n), n) { for (int i = 0; i < n; i++) scanf("%lf%lf", &V[i].x, &V[i].y), P[i] = V[i] ; n--; //最后一个重复的点 int e = n, v = n; for(int i = 0; i < n; i ++) for (int j = i + 1; j < n; j ++) if(SegmentProperIntersection(P[i], P[i + 1], P[j], P[j + 1])) V[v++] = GetLineIntersection(P[i], P[i + 1] - P[i], P[j], P[j + 1] - P[j]); sort(V, V + v); v = unique(V, V + v) - V; for (int i = 0; i < v; i++) for (int j = 0; j < n; j++) if (OnSegment(V[i], P[j], P[j + 1])) e++; printf("Case %d: There are %d pieces.\n", T++, e + 2 - v); } return 0; }