Garden Variety Vampire

Time limit1sMemory limit512 MB

Summary

Given three points and n circle radii, decide whether the circles can be placed so their union connects all three points.

Level: Hard8 of 10
Topics: Geometry, Bit manipulation, Dynamic programming
Solved: No attempts yet

Statement

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 because of unpleasantly good weather. 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 a set of variously sized trees he got from Harker Nurseries at suspiciously low prices. Each tree casts a circle-shaped shadow that Dracula can walk across.

Figure G.1: One solution to the second input. Dots mark the garden, mansion, and shed.

Shadows fall directly beneath the trees and do not move throughout the day. Can he replant his trees so that their shadows form one continuous shadow on the ground connecting the three locations?

Input

The input consists of:

Three lines, each containing the integer coordinates $x_i$ and $y_i$ of one gardening location, where $-10^6 \le x_i, y_i \le 10^6$ for each $i$ .
One line with an integer $n$ ( $1 \le n \le 12$ ): the number of trees the Count has acquired.
One line with $n$ integers $s_1 \ldots s_n$ ( $1 \le s_i \le 10^6$ for each $i$ ), the individual radii of the shadows cast by the Count's trees.

Output

If the Count can place the trees so that they connect all three locations, output "possible". Otherwise, output "impossible".

Examples2

Example 1
Input
```
-6 0
6 0
0 6
4
1 3 1 1
```
Expected output
```
impossible
```
Example 2
Input
```
-6 0
6 0
0 6
4
2 3 2 1
```
Expected output
```
possible
```