Problem Statement
Time limit: 4 seconds.
Given is an arrangement of R times C points in a plane: all points (r, c) with integer coordinates such that 0 <= r < R and 0 <= c < C.
We are going to do the following:
- Pick a sequence of four distinct grid points W, X, Y, Z.
- Draw the cyclic polyline determined by those four points - i.e., draw the line segments W-X, X-Y, Y-Z, and Z-W.
- Take the geometric union of those four line segments and call it a figure.
There are multiple types of figures you can obtain this way:
- Type 0: a line segment.
- Type 1: a triangle.
- Type 2: a letter-P shape (a triangle with one side extended).
- Type 3: a concave quadrilateral (with one inner angle strictly greater than 180 degrees).
- Type 4: a convex quadrilateral (with all inner angles strictly smaller than 180 degrees).
- Type 5: a figure-eight shape (i.e., a self-intersecting but not self-overlapping polyline).
For example, consider the following arrangement of 3x6 points, some of them with labels:
.A . .B . .C .D
. . . .E . .
. . .F .G . .
For these points:
- Selecting the sequence {A, B, C, D} produces a type-0 figure (a line segment).
- Selecting the sequence {A, C, B, D} produces the same type-0 figure as the previous example (even though it is obtained as a union of other four line segments).
- Selecting the sequence {A, B, C, F} produces a type-1 figure (a triangle).
- Selecting the sequence {A, C, B, F} produces a type-2 figure (a triangle ABF with the AB side extended to AC).
- Selecting the sequence {D, G, E, A} produces a type-3 figure (a concave quadrilateral DGEA with GEA as the concave angle).
- Selecting the sequence {A, E, G, D} produces the same type-3 figure as the previous example.
- Selecting the sequence {A, E, D, G} produces a different type-3 figure from the previous two (this one has AED as the concave angle).
- Selecting the sequence {A, B, G, F} produces a type-4 figure.
- Selecting the sequence {A, C, G, F} produces a different type-4 figure.
- Selecting the sequence {A, E, G, F} produces yet another type-4 figure.
- Selecting the sequence {A, C, F, G} produces a type-5 figure (the self-intersecting polyline A-C-F-G-A, with segments CF and GA intersecting).
Two figures are only considered identical if they are the exact same set of points. That is, figures that differ by translation and/or rotation are considered distinct.
You are given R and C.
Return a
Definition
- Class:
- ClassifyQuads
- Method:
- classify
- Parameters:
- int, int
- Returns:
- int[]
- Method signature:
- int[] classify(int R, int C)
- (be sure your method is public)
Constraints
- R will be positive.
- C will be positive.
- R * C (i.e., the number of points) will not exceed 3,000.
Examples
1
20
Returns: {153, 0, 0, 0, 0, 0 }
Valid figures are precisely all horizontal line segments of length 3 or more.
2
1000
Returns: {995006, 997002000, 667995352, 0, 500248257, 496507 }
Valid type-0 figures are still only horizontal line segments that are long enough, but now they can be in either row. There is no way to draw a valid concave quadrilateral. Each valid convex quadrilateral corresponds to one possible way of choosing a point in the top row, another point in the top row to its right, and then two points in the bottom row with the second one to the left of the first one. There are W = (1000*999/2)^2 ways to do that. Please remember to use the correct modulus (10^9 + 7) when calculating the return values. E.g., note that element 4 of the return value (500,248,257) is the value W, modulo 1,000,000,007.
3
4
Returns: {3, 120, 336, 144, 276, 552 }
30
100
Returns: {1076732, 601545463, 368303677, 215401959, 360883318, 721766636 }
54
55
Returns: {1052920, 494344761, 773725141, 35530307, 839525601, 679051195 }
5
6
Returns: {64, 2784, 11928, 14952, 16328, 32656 }
2
20
Returns: {306, 6840, 91200, 0, 36100, 72200 }
30
100
Returns: {1076732, 601545463, 368303677, 215401959, 360883318, 721766636 }
100
30
Returns: {1076732, 601545463, 368303677, 215401959, 360883318, 721766636 }
17
23
Returns: {17785, 7815976, 76165536, 818485716, 647774528, 295549049 }
59
36
Returns: {538027, 276262781, 639232529, 345239525, 997451512, 994903017 }
132
17
Returns: {607693, 505458793, 234828373, 87115656, 846726076, 693452145 }
26
79
Returns: {504602, 153718095, 75666342, 585432711, 191430838, 382861676 }
51
27
Returns: {225348, 346829884, 541779076, 149249785, 488181400, 976362800 }
1
7
Returns: {10, 0, 0, 0, 0, 0 }
51
31
Returns: {297614, 525705812, 913769814, 300056752, 434652762, 869305524 }
21
53
Returns: {146898, 182696076, 454498898, 353507000, 575879313, 151758619 }
61
15
Returns: {99427, 101183396, 563618521, 347603677, 775460995, 550921983 }
29
31
Returns: {95625, 96246492, 108709625, 909368447, 508120770, 16241533 }
48
36
Returns: {355218, 686351912, 989871440, 322613384, 930963000, 861925993 }
39
44
Returns: {350497, 672359440, 743397536, 182859887, 915675573, 831351139 }
16
187
Returns: {1080995, 565606847, 814373487, 473165838, 589855161, 179710315 }
9
171
Returns: {291107, 481745864, 260266150, 306899751, 292659952, 585319904 }
75
24
Returns: {386465, 775670476, 12720804, 121061202, 862434625, 724869243 }
70
33
Returns: {636722, 642210033, 942104423, 939664221, 8104262, 16208524 }
7
333
Returns: {694647, 675494633, 411531440, 971603863, 599444644, 198889281 }
45
43
Returns: {446327, 964982704, 801372060, 787041727, 308226711, 616453422 }
31
96
Returns: {1060463, 517236131, 493111618, 859110567, 47700389, 95400778 }
27
50
Returns: {216600, 326766370, 249983368, 955830662, 661880397, 323760787 }
44
37
Returns: {315617, 574033912, 406961743, 509142129, 725367276, 450734545 }
36
52
Returns: {417126, 872986096, 662973443, 418856738, 400238539, 800477078 }
11
23
Returns: {7352, 2091872, 19777152, 136892688, 111050172, 222100344 }
145
20
Returns: {1008433, 248330387, 245305439, 595152196, 392884945, 785769890 }
17
133
Returns: {617018, 540010613, 301909622, 855136756, 34343905, 68687810 }
39
15
Returns: {40158, 26296488, 316589376, 175064920, 278541563, 557083126 }
63
25
Returns: {295755, 519491828, 396681775, 301216296, 602394991, 204789975 }
39
72
Returns: {941975, 953196990, 376704331, 582705607, 649443026, 298886045 }
29
2
Returns: {702, 21924, 423864, 0, 164836, 329672 }
36
81
Returns: {1015841, 306569175, 547002962, 234399268, 618193999, 236387991 }
1
3000
Returns: {4492503, 0, 0, 0, 0, 0 }
2
1500
Returns: {2242506, 368252979, 252976424, 0, 938053659, 876107311 }
5
600
Returns: {1222515, 555665579, 952433931, 557033438, 694205174, 388410341 }
23
130
Returns: {1074218, 565528073, 989755175, 203635798, 875142102, 750284197 }
37
81
Returns: {1074688, 591863823, 863977350, 247892240, 525595604, 51191201 }
47
63
Returns: {1048166, 464130219, 692569705, 265222487, 742026311, 484052615 }
160
18
Returns: {999568, 182076247, 145431640, 628044019, 479244305, 958488610 }
996
3
Returns: {1480563, 450731619, 228322965, 428443181, 961944379, 923888751 }
1423
2
Returns: {2017820, 875402012, 798036243, 0, 644125848, 288251689 }
3000
1
Returns: {4492503, 0, 0, 0, 0, 0 }