Hide

Problem D
Find Poly

/problems/findpoly/file/statement/en/img-0001.png

Consider a set of line segments in a 2D plane.

For any set of line segments $L$, define $P(L)$ as the set of all endpoints of the line segments in $L$.

Two line segments are said to be connected if they share an endpoint.

Given a set of line segments $U$, we say that a geometric figure (“figure” for short) is a set $S$ of one or more line segments, $S \subseteq U$, for which

  1. for any two points $p_1$ and $p_2$ in $P(S)$, we can reach $p_2$ from $p_1$ by tracing along one or more connected line segments, and

  2. for every line segment $e$ in $S$, all line segments of $U$ that are connected to $e$ are also in $S$.

A polygon is a geometric figure $S$ for which it is possible to trace a path starting from some endpoint $p$ and ending at $p$ using every line segment in $S$ exactly once and visiting each point in $P(S)$ other than $p$, exactly once, visiting $p$ only at the beginning and end of the path.

See Figure 1 which has $10$ figures of which $a$, $b$, $e$, and $f$ are polygons. The dots are the end points of the line segments.

\includegraphics[width=0.5\textwidth ]{findpoly/problem_statement/fig1.pdf}
Figure 1: $10$ figures, $4$ polygons

Note that $b$ is self-intersecting but that the intersection is not at the end points of the intersecting line segments. Similarly $c$ and $d$ as well as $e$ and $f$ intersect but are not connected.

Your task is to count the total number of figures and identify how many are polygons.

Input

The input is a series of lines terminated by end-of-file. Each line will have one or more line segments of the form:

    (x1,y1),(x2,y2);

where (x1,y1) is one end point and (x2,y2) is the other end point, and $0 \leq x1, y1, x2, y2 \leq 99$. All coordinates are integers.

The separator characters, “(),;”, may be preceded or followed by white space. A line may be at most $100$ characters long.

There will be at most $200$ line segments. A given line segment will only appear once in the input and none will be of length $0$.

Line segments are not directed so the order of the end points in the line segment is not significant. The order of the line segments in the input is also not significant.

Output

Print a single line containing two integers separated by a single space. The first number should be the total number of figures and the second should be the number of polygons found.

In the first example below, the points correspond to the picture in Figure 1.

Sample Input 1 Sample Output 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);
10 4
Sample Input 2 Sample Output 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);
7 2

Please log in to submit a solution to this problem

Log in