西安集训D1T1 欧拉回路 - 欧拉定理

结论题

问题描述

平面上给出$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)$之间。

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

测试点编号 N= 特殊性质
1 4
2,3 5
4,5 6
6 7
7,8 300 在最后一条线段出现前,不会产生交点
9,10 300

Solution

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

官方题解:

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

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

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

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

TODO