KGP13F - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Editorialist: Jingbo Shang

DIFFICULTY:

Easy

PREREQUISITES:

Pick’s Theorem

PROBLEM:

Give a 4-point polygon (integer coordinates), find out how many integer points inside or on the border of that polygon.

EXPLANATION:

This problem is really classical. Let me introduce the Pick’s Theorem first.

Area = # Inner Integer Points + # Border Integer Points / 2 - 1

To calculate the Area, we can use cross product.

So the remain part is to get the number of integer points on its border. That equals to count how many integer points on the segment (0,0) - (dx, dy). This can be solved by Greatest Common Divisor (gcd).

# Integer Points on Segment = gcd(dx, dy) + 1

which including the two ends.

Combining these together and applying the Pick’s Theorem, we finally get the total integer points inside or on the border.

2

please explain

what is (dx, dy) ???

1 Like
3

dx=x2-x1, dy=y2-y1 where (x1,y1) and (x2,y2) are end points of polygon’s edge