17571번 - Garden Variety Vampire 다국어

문제

Count Dracula is a voracious (as well as carnivorous) gardener. He keeps a small garden within easy walking distance of his eponymous mansion, and naturally also near to his eponymous potting shed.

Recently, the Count has had to cut back his gardening time sharply on account of adversely excellent weather conditions. His prize Deadly Nightshades are starting to feel neglected.

He would like to pave a shaded path between the garden, the mansion, and the shed using an ensemble of variously-sized trees he’s obtained from Harker Nurseries at suspiciously low prices. Each tree casts a circle-shaped shadow that Dracula can walk across.

Figure G.1: Illustration of a solution to the second sample input. Dots mark the garden, mansion and shed.

Is it possible for him to re-plant his trees in such a way that they cast a continuous shadow on the ground connecting the three given locations? You may assume shadows are directly beneath the trees and do not move throughout the day.

입력

The input consists of:

• three lines each containing the integer co-ordinates of x_i and y_i, each the planar coordinates of one gardening location where (−10⁶ ≤ x_i, y_i ≤ 10⁶ for each i).
• one line with an integer n, (1 ≤ n ≤ 12): the number of trees the Count has acquired.
• one line containing n integers s₁ . . . s_n (1 ≤ s_i ≤ 10⁶ for each i), the individual radii of the shadows cast by the Count’s tree collection.

출력

If the Count can place the trees in such a way as to connect all of the sites, output “possible”. Otherwise, output “impossible”.

제한

힌트