QOJ.ac

QOJ

حد الوقت: 1 s حد الذاكرة: 1024 MB مجموع النقاط: 100

#2751. 寻找 Poly

الإحصائيات

考虑二维平面上的一组线段。 对于任意线段集合 $L$,定义 $P(L)$ 为 $L$ 中所有线段端点的集合。 如果两条线段共享一个端点,则称它们是相连的。 给定一组线段 $U$,我们称一个几何图形(简称“图形”)为一个或多个线段的集合 $S$($S \subseteq U$),且满足:

  1. 对于 $P(S)$ 中的任意两点 $p_1$ 和 $p_2$,可以通过沿着一条或多条相连的线段追踪从 $p_1$ 到达 $p_2$。
  2. 对于 $S$ 中的每一条线段 $e$,$U$ 中所有与 $e$ 相连的线段也必须在 $S$ 中。

多边形是一个几何图形 $S$,且满足:可以从某个端点 $p$ 出发,沿着 $S$ 中的每一条线段恰好走一次,并回到 $p$,且在路径中访问 $P(S)$ 中除 $p$ 以外的每个点恰好一次,仅在路径的起点和终点访问 $p$。

参见图 1,其中有 10 个图形,其中 a、b、e 和 f 是多边形。点是线段的端点。 注意,b 是自相交的,但交点不是相交线段的端点。同样,c 和 d 以及 e 和 f 虽然相交,但它们并不相连。 你的任务是计算图形的总数,并识别其中有多少个是多边形。

输入格式

输入是一系列以文件结束符(EOF)结尾的行。每一行包含一个或多个形式如下的线段: $(x1,y1),(x2,y2);$ 其中 $(x1,y1)$ 是一个端点,$(x2,y2)$ 是另一个端点。$0 \le x1, y1, x2, y2 \le 99$。所有坐标均为整数。 分隔符字符 “(),;” 前后可能包含空格。一行最多 100 个字符。 最多有 200 条线段。给定的线段在输入中只会出现一次,且没有长度为 0 的线段。 线段是无向的,因此线段中端点的顺序不重要。输入中线段的顺序也不重要。

输出格式

输出一行,包含两个由空格分隔的整数。第一个数字应该是图形的总数,第二个数字应该是找到的多边形的数量。

样例

样例输入 1

(84,84),(78,84);(68,60),(64,64);(20,85),(15,88);(0,0),(2,8);
(30,60),(30,66);(13,40),(18,38);(15,88),(15,95);(18,38),(8,38);
(31,7),(25,10);(30,66),(26,70);(40,14),(30,19);(5,85),(15,88);
(48,20),(56,26);(84,84),(84,82);(66,82),(70,86);(15,95),(25,90);
(70,86),(66,88);(59,23),(50,27);(15,88),(5,80);(78,84),(74,82);
(60,80),(66,82);(5,85),(5,80);(25,10),(40,14);(20,85),(25,90);
(20,60),(30,66);(13,36),(14,30);(30,60),(20,60);(64,64),(60,60);
(31,7),(30,19);(15,88),(25,90);(68,60),(76,64);(8,38),(13,40);
(5,85),(15,95);(0,0),(10,4);(10,30),(14,30);(74,82),(70,86);
(10,30),(12,43);(6,10),(10,4);(5,80),(20,85);(6,10),(2,8);
(60,80),(66,88);(84,82),(74,82);(12,43),(13,36);

样例输出 1

10 4

样例输入 2

(45,26),(88,34);(39,6),(67,8);(73,52),(92,38);(63,35),(18,61);
(34,23),(46,10);(2,75),(86,47);(26,18),(95,36);(59,78),(49,95);
(63,95),(67,80);(23,12),(33,46);(33,1),(46,10);(63,78),(2,75);
(2,33),(11,31);(99,98),(18,5);(88,34),(49,95);(25,43),(46,10);
(66,1),(2,75);(17,59),(2,33);(85,7),(85,59);(51,56),(63,95);
(1,48),(46,7);(66,49),(57,84);(59,78),(63,35);(0,49),(69,83);
(75,82),(51,56);(67,8),(92,38);(25,43),(86,47);(54,33),(12,42);
(87,12),(57,84);(37,92),(84,90);(18,61),(12,42);(66,49),(95,36);
(85,7),(73,52);(1,48),(99,98);(53,26),(11,31);(34,23),(86,47);
(22,91),(55,59);(23,12),(75,6);(66,1),(33,1);(33,46),(97,41);
(87,12),(66,49);(92,38),(8,19);(54,33),(97,41);(45,26),(7,53);
(39,6),(85,59);(63,78),(34,23);(76,9),(18,5);(67,80),(17,59);
(25,43),(66,1);(75,82),(53,26);(0,49),(18,61);(12,42),(19,3);
(33,1),(63,78);(76,9),(46,7);(8,19),(84,90);(8,19),(37,92);

样例输出 2

7 2

说明

在第一个样例中,点对应于图 1 中的图形。

图 1:10 个图形,4 个多边形

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.