CutCutCut | Topcoder Archive

Problem Statement

You have a square plate. Its dimensions are 10000 x 10000. The bottom left corner has coordinates (0, 0), the bottom right is (10000, 0), and the top right is (10000, 10000).

You are going to make Q cuts, one after another. For each cut you are given two points (X1[i], Y1[i]) and (X2[i], Y2[i]) on different sides of the square. You should cut the square along the straight line segment that connects those two points. The cuts are in a general position (see Constraints).

After each query, determine the current number of pieces into which the square is divided at that moment. Return a int[] with Q elements: those numbers of pieces.

Definition

Class:: CutCutCut
Method:: findPieces
Parameters:: int[], int[], int[], int[], int
Returns:: int[]
Method signature:: int[] findPieces(int[] X1, int[] Y1, int[] X2, int[] Y2, int Q)
(be sure your method is public)

Constraints

Q will be between 1 and 500, inclusive.
Each of X1, Y1, X2 and Y2 will have exactly Q elements.
All the given segment endpoints will be distinct.
All the given segment endpoints will be on the boundary of the square.
None of the given segment endpoints will be in the corners of the square.
For each segment, its endpoints will lie on different sides of the square.
No three cuts will intersect at the same point.

Examples

```
{1, 2, 3}
```
```
{0, 0, 0}
```
```
{1, 2, 3}
```
```
{10000, 10000, 10000}
```
```
3
```
```
Returns: {2, 3, 4 }
```
Here we first cut the plate along the segment joining (1,0) and (1,10000), so we have 2 pieces now, next we cut along segment joing (2,0) and (2,10000)(cutting the right piece from pervious), so we have 3 pieces now, similarly after the 4th cut we have 4 pieces.
```
{0, 5000}
```
```
{5000, 10000}
```
```
{10000, 5000}
```
```
{5000, 0}
```
```
2
```
```
Returns: {2, 4 }
```
Here we first cut the plate along the segment joining (0,5000) and (10000,5000), getting 2 pieces(equal pieces), then when we cut along segment joining (5000,1000) and (5000,0) we get 4 pieces(cutting previous 2 pieces again in equal parts).

{1,0,3,9997}

{0,1,0,10000}

{1,10000,0,10000}

{10000,1,3,9997}

Returns: {2, 4, 7, 8 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.