DMPG '15 B6 - Bad S'mores

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.4s
Memory limit: 32M

Problem type

It is time to set up camp for the night! Bob has built a nice campfire to help everybody keep warm during the night. Every tent would like to be close to the fire, but there is one small problem — Bob's s'more ingredients were expired and many people got sick eating them. As a result, every tent should be close to the bathroom as well.

The campsite can be represented as a Cartesian plane.

  • The campfire is located at (x_f, y_f) and can provide warmth to tents of at most distance r away from the fire as the crow flies (Euclidean distance).
  • The washroom is located at (x_w, y_w), and can be reached by walking along the paths on the campsite.
  • The paths in the campsite form a grid, such that each path can be described as a line in the form of x=i or y=i, where i is an integer. There is a path for every integral value of i, so in total the number of paths is infinite. A tent should be within walking distance along a path (Manhattan distance), such that the distance to the washroom is less than or equal to l. A tent can be set up only on an integer coordinate — (x, y) such that x and y are integers — and cannot occupy the same position as the fire or washroom.

Can you help Bob determine the maximum amount of tents that can be set up?

Input Specification

The first line will contain three integers, x_f, y_f, and r. The second line will contain another three integers, x_w, y_w, and l. -100\,000 \le x_f, y_f, x_w, y_w \le 100\,000 and 1 \le r,l \le 100\,000.
For at least 20\% of the marks, -100 \le x_f, y_f, x_w, y_w \le 100 and 1 \le r,l \le 100.

Output Specification

One integer, the maximum number of tents that can be set up so that it is within range of the fire and the washroom.

Sample Input

2 2 2
5 2 3

Sample Output


Diagram for Sample Input

The red circle represents the area the campfire covers, and the blue lines represent the area the washroom covers. Each green dot is a possible location to set up a tent.


  • 0
    harry7557558  commented on March 9, 2020, 4:55 a.m. edited

    Can the washroom occupy the fire? (Batch #5 Case #3)