Rectangle Rotation

Description:

A rectangle with sides equal to even integers a and b is drawn on the Cartesian plane. Its center (the intersection point of its diagonals) coincides with the point (0, 0), but the sides of the rectangle are not parallel to the axes; instead, they are forming 45 degree angles with the axes.

How many points with integer coordinates are located inside the given rectangle (including on its sides)?

Example

For a = 6 and b = 4, the output should be
rectangleRotation(a, b) = 23.

The following picture illustrates the example, and the 23 points are marked green.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer aA positive even integer.

    Constraints:
    2 ≤ a ≤ 50.

  • [input] integer bA positive even integer.

    Constraints:
    2 ≤ b ≤ 50.

  • [output] integerThe number of inner points with integer coordinates.

Tests:

Explain:

a17b87ea843a52e8ce44a35109bca772af4ba2631

therefore 4 blue edges make 45 degrees angles so the 4 edges are corresponding 4 expressions:

  • f1(x,y) = x + y + u = 0
  • f2(x,y) = x + y – u = 0
  • f3(x,y) = x – y + v = 0
  • f4(x,y) = x – y – v = 0

therefore point O(0,0) is in the rectangle, So

  • f1(0,0) = u > 0
  • f2(0,0) = -u < 0
  • f3(0,0) = v > 0
  • f4(0,0) = -v < 0

If 1 point P(x,y) is in the rectangle then demands 4 conditions:

  • f1(x,y) = x + y + u > 0
  • f2(x,y) = x + y – u < 0
  • f3(x,y) = x – y + v > 0
  • f4(x,y) = x – y – v < 0

Mean: |x + y| < u and |x – y| < v

Now finding u, v:

Draws more 2 red lines perpendicular with 2 edges of the rectangle, we have right angled triangles, So u = a/sqrt(2), v = b/sqrt(2).
Solution(C#):


int rectangleRotation(int a, int b) {
   int r = 0;
	for (int x = -a - b; x &amp;amp;amp;amp;amp;lt;= a + b; x++) {
		for (int y = -a - b; y &amp;amp;amp;amp;amp;lt;= a + b; y++) {
			if (2 * (x - y) * (x - y) &amp;amp;amp;amp;amp;lt;= a * a &amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp; 2 * (x + y) * (x + y) &amp;amp;amp;amp;amp;lt;= b * b)
                r++;
		}
	}
	return r;
}
Advertisements

4 thoughts on “Rectangle Rotation

  1. no says:

    this makes little sense. why would spanning the perimeter (-a-b to a+b) yield anything? There’s no shape information to that data. (ex. if a is 4 and b is 6, that range is the same as if a is 2 and b is 10)

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s