PEG Judge - CCC00 Stage 2

2000 Canadian Computing Competition, Stage 2

Day 2, Problem 3: Extension Cords

Harry the handyman needs to plug in his table saw and his arc welder at his work location. Since they each draw a lot of current, he must plug them into outlets on two different electrical circuits. Several outlets are available; each outlet is on one of several circuits. Harry has a number of extension cords of various lengths. Can Harry join some of his extension cords together so as to plug in the saw and the welder to different circuits at the same time?

Input

The first line of input contains four numbers: x, y, n, m. x and y, both real numbers, give the coordinates of Harry's work location. n, an integer between 1 and 100, gives the number of extension cords. m, an integer between 1 and 100, gives the number of outlets. For each extension cord, a line follows which gives its length, a positive integer less than 500. For each outlet, a line follows containing a, b, and c. a and b, both real numbers, give the coordinates of the outlet. c, an integer, gives the circuit number to which the outlet is connected.

There are no obstructions on the floor so Harry can run a string of cords directly from any outlet to his work location.

Output

If Harry can plug in his equipment, print the coordinates of the first pair of outlets to which Harry can connect, in the format below. Otherwise, print "Harry is helpless."

We define the "first pair" of outlets as the pair which has the earliest outlest (in the order of the input file).
That is, a pair comes before another pair if the first outlet of the first pair is earlier in the input than the first outlet of the second pair. If there is a tie with the first outlet, then consider the orders of the second outlets.

Sample Input

100.0 100.0 3 3
7
8
6
100.0 106.0 1
110.0 90.0 2
89.0 111.0 3

Sample Output

Harry can connect to outlets at (100.0, 106.0) and (110.0, 90.0).

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 19, 2009

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

Comments (Search)

jimgao on Nov 03, 2016 - 5:45:38 pm UTC Spelling

(1/1)

In Output Specs:

We define the "first pair" of outlets as the pair which has the earliest [b]outlest[/b] (in the order of the input file).

In Output Specs:

We define the "first pair" of outlets as the pair which has the earliest outlest (in the order of the input file).

xiaowuc1 on Jun 30, 2014 - 2:01:31 am UTC Can the input for test case 5 be validated?

(1/0)

I don't believe it adheres to the given input format - I've made several submissions that purposefully TLE when the input is correctly read and my program crashes on test case 5.

I don't believe it adheres to the given input format - I've made several submissions that purposefully TLE when the input is correctly read and my program crashes on test case 5.

zzh8829 on Jun 30, 2014 - 4:38:06 pm UTC Re: Can the input for test case 5 be validated?

(0/1)

Well, test cases should be fine considering 6 of us solved this problem.

Well, test cases should be fine considering 6 of us solved this problem.

xiaowuc1 on Jun 30, 2014 - 4:49:34 pm UTC Re: Can the input for test case 5 be validated?

(3/0)

You all solved it in C++. If you all use the same exact input-parsing code, you'll generate exactly the same result.

I'll write up a solution in C++ and report back.

EDIT: After solving it in C++, I verify that test case 5 is invalid. The test case clearly indicates that m = 4, but on line 1, only three numbers are present.

This also isn't the first time that CCC test data have been invalid. The problem is that essentially all C++ solutions parse input exactly the same way, so they work with exactly the same data and will therefore jump to the same conclusion. Take a look at [url=http://wcipeg.com/problem/ccc04s2p1#comment5893]this problem[/url], for example.

You all solved it in C++. If you all use the same exact input-parsing code, you'll generate exactly the same result.

I'll write up a solution in C++ and report back.

EDIT: After solving it in C++, I verify that test case 5 is invalid. The test case clearly indicates that m = 4, but on line 1, only three numbers are present.

This also isn't the first time that CCC test data have been invalid. The problem is that essentially all C++ solutions parse input exactly the same way, so they work with exactly the same data and will therefore jump to the same conclusion. Take a look at this problem, for example.