Usaco Oct10 Silver

Part of USACO Oct10

**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Two problems numbered 6 through 7
**********************************************************************

Problem 6: Dinner Time [Jelle van den Hooff, 2009]

Farmer John's N (1 <= N <= 1,000) cows conveniently numbered 1..N
are participating in the IOI in Bulgaria. The cows like the Bulgarian
sun and are enjoying their holiday. All seems well.

This changes around dinner time. The restaurant is rather small,
having only M (1 <= M <= N) cow seats conveniently numbered 1..M.
Each cow starts at a location CX_i, CY_i (-1,000,000 <= CX_i <=
1,000,000; -1,000,000 <= CY_i <= 1,000,000); the seats can be found
at SX_j, SY_j (-1,000,000 <= SX_j <= 1,000,000; -1,000,000 <= SY_j
<= 1,000,000).

The cows have a very efficient (though primitive) method to distribute
themselves into the seats. As soon as a cow is certain she will get
to a seat first, she rushes there as fast as she can (all cows runs
equally fast).

Farmer John's cows, like all prize cows, have no problem jumping
over seats, tables, or other cows, so they can run in a straight
line. When multiple cows can reach a seat at the very same time,
the oldest cow (the one appearing earlier in the input data) gets
the seat.  Likewise, when a cow can be the first to reach multiple
seats she will also choose the one appearing earliest in the input.

Some cows won't be able to eat dinner, and those hungry cows are
collectively planning to steal Farmer John's very own food. Farmer
John would like a list of cows he should be wary of. (In the case
when there are no hungry cows, output 0). Can you help him?

NOTE: Standard distance calculations will likely require an
intermediate result that will fit into a 64-bit integer but not
into a 32-bit integer.

PROBLEM NAME: dinner

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 contains two space separated integers: CX_i
        and CY_i

* Lines N+2..N+M+1: Line j+N+1 contains two space separated integers:
        SX_j and SY_j

SAMPLE INPUT (file dinner.in):

2 1
0 1
1 0
1 10

INPUT DETAILS:

2 cows: Cow 1 starts at (0, 1) and cow 2 at (1, 0). There
is only 1 seat at (1, 10).

OUTPUT FORMAT:

* Lines 1..N-M: Line i contains the number of the ith cow that Farmer
        John should be wary of. The cow numbers should be listed in
        increasing order.

SAMPLE OUTPUT (file dinner.out):

2

OUTPUT DETAILS:

Cow 1 is closer to the seat than cow 2, so cow 1 will get the only seat.

**********************************************************************

Problem 7: Lake Counting [Hal Burch and Rob Kolstad, 2004]

Due to recent rains, water has pooled in various places in Farmer
John's field, which is represented by a rectangle of N x M (1 <= N
<= 100; 1 <= M <= 100) squares. Each square contains either water
('W') or dry land ('.'). Farmer John would like to figure out how
many ponds have formed in his field.  A pond is a connected set of
squares with water in them, where a square is considered adjacent
to all eight of its neighbors.

Given a diagram of Farmer John's field, determine how many ponds he has.

PROBLEM NAME: lkcount

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M characters per line representing one row of Farmer
        John's field.  Each character is either 'W' or '.'.  The
        characters do not have spaces between them.

SAMPLE INPUT (file lkcount.in):

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

OUTPUT FORMAT:

* Line 1: The number of ponds in Farmer John's field.

SAMPLE OUTPUT (file lkcount.out):

3

OUTPUT DETAILS:

There are three ponds: one in the upper left, one in the lower left,
and one along the right side.

**********************************************************************