Connection Status:
Competition Arena > CutCutCut

CutCutCut

SRM 763 · 2019-07-16 · by vivek1998299

SRM 763 · 2019-07-16 · by vivek1998299 · Geometry
Class Name: CutCutCut
Return Type: int[]
Method Name: findPieces
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>, int)
Problem Statement

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.

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
0)
{0, 0, 1476, 10000, 2780, 10000}
{6062, 4402, 10000, 4529, 0, 2773}
{3373, 5725, 1400, 159, 10000, 2603}
{0, 0, 0, 10000, 921, 10000}
6
Returns: {2, 4, 7, 9, 12, 14 }
1)
{10000, 10000, 866, 5912, 10000}
{7283, 2180, 0, 10000, 2099}
{9857, 0, 9053, 10000, 0}
{10000, 1852, 10000, 577, 9078}
5
Returns: {2, 3, 5, 8, 12 }
2)
{6380}
{0}
{10000}
{2137}
1
Returns: {2 }
3)
{4061}
{10000}
{10000}
{5080}
1
Returns: {2 }
4)
{0, 5949, 9945}
{4989, 10000, 0}
{2259, 0, 452}
{0, 555, 10000}
3
Returns: {2, 4, 6 }
150)
{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.

151)
{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).

Submissions are judged against all 155 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CutCutCut with a public method vector<int> findPieces(vector<int> X1, vector<int> Y1, vector<int> X2, vector<int> Y2, int Q) · 155 test cases · 2 s / 256 MB per case

Submitting as anonymous