结论题

问题描述

平面上给出 $N - 1$ 个点，按照给出的 $N$ 个坐标的顺序将这 $N - 1$ 个点连在一起，保证最终会回到起点，求划分出的平面区域个数。

输入格式

共若干组询问，当 $N$ 为 $0$ 时结束。

对于每组询问：

第一行包含一个正整数 $N$ 。

接下来 $2N$ 个整数，每两个表示一个点。

输出格式

对于每组询问输出一行一个整数，表示划分出的平面区域个数。

样例输入

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

样例输出

2
5

数据规模与约定

对于所有数据，询问组数 $\leq 25$ ， $4\leq N \leq 300$ ，点的坐标在 $(-300,300)$ 之间。

保证不会出现两条线段重合的情况。

Solution

根据欧拉公式，平面图的点数-边数+面数=2，只要计算有多少个线段交点，多少条边即可。

官方题解：

欧拉定理：设平面图的顶点数、边数和面数分别是 $V,E,F$ ，则有 $V+F-E=2$ 。

●顶点个数 $V$ : $n$ 个顶点+交点，注意存在三线共点的情况，找到所有交点后要去重，利用去重函数unique。

●棱数 $E$ ： $n$ 条棱，若有交点棱数要多，注意存在三线共点的情况，并不是简单地一个交点就多以条棱，而是凡是穿过交点的边棱数都++，所有要遍历边判断交点是否在边上，满足就 $E$ ++。

代码懒的写了，有空再补。

TODO