That Nice Euler Circuit

Time limit1sMemory limit128 MB

Summary
Given the vertices of a closed polygonal Euler circuit whose segments may cross, count the connected regions the drawing divides the plane into.
Level

Medium7 of 10

Topics
Geometry, Graph, Implementation, Math
Solved
No attempts yet

Problem

Little Joey built a scrabble-like machine that he named Euler, after the great mathematician. In primary school Joey heard the famous story of how Euler founded the study of graphs. The problem in that story was to draw a figure on paper without lifting your pen and finally return to the starting point. Euler proved that this is possible if and only if the (planar) graph you draw has two properties: (1) the graph is connected, and (2) every vertex has even degree.

Joey's Euler machine works in the same spirit. It consists of a pencil touching the paper and a control center that issues a sequence of instructions. The paper is the infinite two-dimensional plane, so you never have to worry about the pencil running off an edge.

The first instruction has the form (X0,Y0)(X_0, Y_0) and moves the pencil to the starting position (X0,Y0)(X_0, Y_0). Each later instruction, also of the form (X′,Y′)(X', Y'), moves the pencil from its current position to the new position (X′,Y′)(X', Y'), drawing a line segment. The new position is always different from the previous one. The final instruction always returns the pencil to the starting position (X0,Y0)(X_0, Y_0). The machine never draws a segment that overlays a segment already drawn, although segments may cross one another.

After all instructions are issued, a figure remains on the paper. Because the pencil is never lifted, this figure is an Euler circuit.

Your task is to count how many pieces (connected regions) the drawn segments divide the paper into.

Input

The input contains at most 2525 test cases. Each test case starts with a line containing an integer N≥4N \ge 4, the number of instructions. The following NN pairs of integers, separated by single spaces, give the instructions; the first pair is the starting position. Every test case has at most 300300 instructions, and every integer coordinate lies in the range (−300,300)(-300, 300). The last instruction of a test case always coincides with the starting position, closing the circuit.

The input terminates with a line containing N=0N = 0, which is not processed.

Output

For each test case, print one line in the format

Case x: There are w pieces.

where xx is the test case number starting from 11, and ww is the number of connected regions into which the figure divides the plane. The single unbounded region outside the figure is counted as one piece (so a simple square gives 22).

Examples3

  1. Example 1

    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
    
    Expected output
    Case 1: There are 2 pieces.
    Case 2: There are 5 pieces.
    
  2. Example 2

    Input
    5
    0 0 0 1 1 1 1 0 0 0
    0
    
    Expected output
    Case 1: There are 2 pieces.
    
  3. Example 3

    Input
    4
    0 0 4 0 2 3 0 0
    0
    
    Expected output
    Case 1: There are 2 pieces.