Another Convex Polygon Problem

You are given a convex polygon with N vertices and M straight lines which divide the polygon into several regions. You must compute the number of regions into which the polygon is divided by the straight lines.

The first line of input contains the number T of test cases. The next lines describe the T test cases. The first line of each test case contains two integer numbers, separated by one blank: the number N of vertices of the convex polygon (3 <= N <= 10) and the number M of straight lines (0 <= M <= 10). The next N lines contain 2 integer numbers X and Y, denoting the coordinates of some vertex of the polygon. The vertices are given in clockwise or anti-clockwise order. Each of the next M lines contains 4 integer numbers: x₁ y₁ x₂ y₂. (x₁,y₁) and (x₁,y₁) are two different points on the straight line. All the X and Y coordinates in the input file are in the range -20…20.

For each test case print a line having the following format: “Number of regions=XXX.”, where XXX is replaced by the number of regions into which the polygon is divided.

2
3 0
0 0
1 1
1 0
3 3
0 0
1 1
1 0
1 2 3 4
1 2 3 4
1 2 3 4

Number of regions=1.
Number of regions=1.

Mugurel Ionut Andreica

Politehnica University of Bucharest Local Team Contest 2007