The Partition of a Cake
TimeLimit:10000MS MemoryLimit:32768KB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description
There is a 1000*1000 square cake. We use knife to cut the cake. The problem is after a series of cutting, how many partitions the cake will has.
Assumption:
The number of the cutting will be no more than 8.
After the cutting, the length of any edge of the partition will no less than 1.
The vertex coordinates of the cake are (0,0)(0,1000)(1000,1000)(1000,0).
The intersections of the cut line and the cake edge are two.
The following Graph is a sample partition. The number of the partitions is 10.
Assumption:
The number of the cutting will be no more than 8.
After the cutting, the length of any edge of the partition will no less than 1.
The vertex coordinates of the cake are (0,0)(0,1000)(1000,1000)(1000,0).
The intersections of the cut line and the cake edge are two.
The following Graph is a sample partition. The number of the partitions is 10.
Input
The first line of the input is the number of the cutting. The following lines contain the information of the cut lines. Each line has 4 integer number, which represent the coordinate of the intersection of the line and the cake edge. After last cake is 0.
Output
The output is the number of the partitions of the cake.
SampleInput
3 0 0 1000 1000 500 0 500 1000 0 500 1000 500 1 0 0 1000 1000 0
SampleOutput
6 2