You are not logged in. Please login at www.codechef.com to post your questions!

×

NICEQUAD - Editorial

1
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

To detect whether the quadrangle has an integer area we will use the Pick theorem which states that the area of a grid polygon can be calculated in the following way S = W + I/2 - 1. Where W is the amount of lattice points strictly inside the polygon and I is the amount of lattice points on its edge. So the area S will be integer if the amount of lattice points on its edge will be even. Now how we will count the amount of lattice points on the edge of a given quadrangle.

Let us consider any quadrangle ABCD the edges of which don’t intersect. Let’s look at its edge AB. The amount of lattice points lying on that edge can be calculated as gcd(|Ax – Bx|, |Ay – By|) + 1, where gcd is the greatest common divisor. Or it will be gcd(|Ax - Bx|, |Ay - By|) – 1 if we don’t count the points on the ends of segment AB.

So now if we count the same value for each edge we will have the following expression for I = gcd(|Ax - Bx|, |Ay - By|) + gcd(|Bx - Cx|, |By - Cy|) + gcd(|Cx - Dx|, |Cy - Dy|) + gcd(|Dx - Ax|, |Dy - Ay|) (1). But we only need to each if that value is odd or even. For two given non-negative integers gcd(a, b) is even iff a and b are both even. So gcd(|Ax - Bx|, |Ay - By|) is even iff |Ax – Bx| and |Ay – By| are both even. Now |Ax – Bx| is even iff Ax and Bx are both even of both odd. So gcd(|Ax - Bx|, |Ay - By|) is even when the Ax and Bx have the same remainder modulo 2 and Ay and By have the same remainder modulo 2. That means that we don’t need to know the exact value of Ax, Ay, Bx, By, but only their remainders modulo 2. That is true for all other points as well. After we find if any of the gcds in (1) are odd or even we can easily determine if I is odd or even.

Next is how to count all the quadrangles with the stated quality. First we need to split the given point into four groups: the first group with x > 0 and y > 0, the second – x > 0 and y < 0, the third x < 0 and y < 0 and the fourth – x < 0 and y > 0. Then in each group we need to split all points of the group into four groups again: the first group with x even and y even, the second – x even and y odd, the third – x odd and y even and the fourth – x odd and y odd. We will count the amount of points in each group and each subgroup as well. After that we can iterate over all possible variants of taking points from the group. Surely to form a triangle we have to take one point from each group of the first type. Then we try all possible assignment of points from the subgroups.

There are in total 4^4 different types of quadrangles we can form. For each type we know the amount of quadrangles of that type and we can determine if the area of quadrangles of such type is an integer. So we try all those types and if the area is an integer we add the amount of those quadrangles to the answer.
The complexity of the described algorithm is O(n).

This question is marked "community wiki".

asked 28 Nov '12, 17:29

admin's gravatar image

0★admin ♦♦
19.7k350498541
accept rate: 35%

1

Could you please explain why gcd(|Ax – Bx|, |Ay – By|) + 1 equals to the number of lattice points on the the edge AB?

(28 Jun '13, 15:52) tvhong4★

"Ax and Bx are both even of(or*) both odd."

(03 Sep '14, 22:17) atulthetricky2★

Let (m, n) be a lattice point, and let l be the lattice line segment with endpoints (0, 0) and (m, n). Let gcd(m, n) = d. Then gcd(m /d , n/ d ) = 1, and the point, (m/ d , n/ d ) is visible. The lattice points on l other than (0, 0) and (m, n) must be ( m/ d , n/ d ),( 2m/ d , 2n/ d ),( 3m/ d , 3n/ d ), . . . ,( (d−1)m/ d , (d−1)n/ d ). Thus, there are d−1 points on l not including its endpoints

link

answered 27 Aug '13, 08:30

murdocc007's gravatar image

3★murdocc007
4727
accept rate: 12%

For the question "why gcd(|Ax – Bx|, |Ay – By|) + 1 equals to the number of lattice points on the the edge AB?"

Refer http://math.stackexchange.com/questions/918362/what-is-the-number-of-integer-coordinates-on-a-line-segment/918367#918367

link

answered 03 Sep '14, 22:20

atulthetricky's gravatar image

2★atulthetricky
01
accept rate: 0%

edited 03 Sep '14, 23:17

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,497
×3,709
×6
×2

question asked: 28 Nov '12, 17:29

question was seen: 3,889 times

last updated: 03 Sep '14, 23:17