Woburn Challenge 2015-16 Round 2 - Junior Division

Problem VI: Return of the Jedi

“Coding? What do you mean, you're coding? Coding what, Artoo? No, wait! Artoo! This is no time for heroics!”

Things are coming to a head on the forest moon of Endor. E (1 ≤ E ≤ 100) friendly Ewoks have been sent out to scout the area, in preparation for an attack on the shield generator protecting the Empire's devastating weapon – the Death Star. From a bird's eye view, the forest can be modelled as a Cartesian plane, with the i-th Ewok located at integer coordinates (Xei, Yei) (0 ≤ Xei, Yei ≤ 1000).

Unfortunately, the Empire seems to be onto the rebels' plan! S (1 ≤ S ≤ 100) stormtroopers have similarly been dispatched into the woods to guard the perimeter, with the i-th one stationed at coordinates (Xsi, Ysi) (0 ≤ Xsi, Ysi ≤ 1000). Each stormtrooper is also classified as one of four types, depending on the weaponry they carry. Namely, the i-th stormtrooper is of type Wi (1 ≤ Wi ≤ 4). The BlasTech E-11 rifles may be the standard weapon of these imperial stormtroopers, but most don't know that there are variants of the E-series weapons which serve different purposes and possess different strengths for attacking an opponent. The variants are:

  1. The E-11 blaster rifle – a powerful and compact weapon that is the most widely used in the galaxy.
  2. The E-11b blaster rifle – an expert version of the standard E-11 with expensive cooling units.
  3. The E-11s sniper blaster rifle – a modified blaster for long-range use by imperial scout troopers.
  4. The E-15 "Vindicator" sniper blaster rifle – a heavy-power weapon with a short design, making it greatly feared throughout the galaxy.

Each stormtrooper can hit targets that are located up to a distance of R (1 ≤ R ≤ 10,000) units away with deadly accuracy. Ewoks are quick enough to handle any number of a single type of stormtrooper using their nifty spears and slingshots. However, any more than a single type of stormtrooper poses a risk to them, since varying types of blasters are much more difficult to handle. In other words, any given Ewok is in danger if there are two or more types of stormtroopers which are no more than R units away.

As a reminder, if the absolute difference between the x-coordinates of two points is x, and the absolute difference between their y-coordinates is y, then the (Euclidean) distance between them is √(x2 + y2).

How many of the E Ewoks are in danger?

Input Format

The first line of input consists of three space-separated integers S, E, and R.
The next S lines each consist of three space-separated integers Wi, Xsi and Ysi, for i = 1..S.
The next E lines each consist of two space-separated integers Xei and Yei, for i = 1..E.
All pairs of coordinates in the input are distinct — i.e. no two individuals (Ewoks or stormtroopers) are at the same location.

Output Format

Output a single integer – the number of Ewoks that are in danger.

Sample Input

4 6 5
1 10 10
1 11 9
2 16 10
3 11 10
1 1
12 10
22 10
7 12
10 6
13 15

Sample Output

3

Explanation

There are four stormtroopers with the first two carrying an E-11, the third carrying an E-11b, and the fourth carrying an E-11s.
The 2nd Ewok is in danger due to being only 2 units away from the 1st stormtrooper (type 1) and 4 units away from the 3rd stormtrooper (type 2).
The 4th and 5th Ewoks are also in danger, as they are within range of the 1st stormtrooper (type 1) and 4th stormtrooper (type 3).
The remaining three Ewoks are safe.

All Submissions
Best Solutions


Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 12, 2015
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...