P4354 [CERC2015] Ice Igloos

A fishing village built on the surface of a frozen lake far north in the arctic is endangered by global warming-fractures are starting to form on the lake surface. The village consists of n igloos of spherical shape, each occupying a circular area of the surface. An igloo can be represented as a circle in the coordinate plane: the center of the circle is a point with integer coordinates, while the radius is a positive floating-point number less than 1 with exactly one fractional digit. Given the locations of possible ice fractures, the villagers would like to know how many igloos are affected by each. Formally, given q queries where each query is a straight line segment defined by the two endpoints, find the number of igloos each segment intersects. A segment intersects an igloo if it has at least one point in common with the interior of the circle.

N/A

N/A

 Central Europe Regional Contest 2015 Problem I