Connection Status:
Competition Arena > CheckerPolygon

CheckerPolygon

TCCC05 Semi 3 · 2005-01-10 · by Yarin

TCCC05 Semi 3 · 2005-01-10 · by Yarin · Geometry, Math
Class Name: CheckerPolygon
Return Type: int[]
Method Name: countSquares
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

A convex polygon is placed on a large checkerboard with the polygon vertices lying on the grid intersections. Calculate the number of light and dark squares lying entirely inside the polygon. Assume that the polygon edges are infinitely thin. In the picture below, 28 light squares and 26 dark squares are enclosed by the polygon. The upper left corner (coordinates 0,0) will always be a dark square.


Create a class CheckerPolygon containing the method countSquares which takes two int[], X and Y, describing the convex polygon. Element i in X and Y is the coordinate for the ith vertex in the polygon. The method should return a int[] containing exactly two elements: the first element is the number of light squares entirely enclosed by the polygon, and the second element the number of dark squares entirely enclosed by the polygon.

Notes

  • The vertices in the polygon may be ordered clockwise or counter-clockwise.

Constraints

  • X and Y will contain between 3 and 50 elements, inclusive.
  • X will contain the same number of elements as Y.
  • Each element in X and Y will be between 0 and 10000, inclusive.
  • The polygon described by X and Y will be convex.
  • There will not be three points lying on the same line.
Examples
0)
{1,2,5,8,11,10,6,4,2}
{7,5,2,1,2,8,11,11,9}
Returns: {26, 28 }

This is the example in the problem statement.

1)
{1,5000,5001,10000,10000,5001,5000,1}
{4999,0,0,4999,5000,9999,9999,5000}
Returns: {25000000, 24990001 }
2)
{1,3,6}
{3,6,1}
Returns: {1, 1 }
3)
{537,127,987,2390}
{173,98,12,107}
Returns: {90908, 90911 }
4)
{10000,10000,0,0}
{0,10000,10000,0}
Returns: {50000000, 50000000 }

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

Coding Area

Language: C++17 · define a public class CheckerPolygon with a public method vector<int> countSquares(vector<int> X, vector<int> Y) · 59 test cases · 2 s / 256 MB per case

Submitting as anonymous