아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

연장 코드

면접 대비

시간 제한1초메모리 제한128 MB

요약
연장선을 두 그룹으로 나누어 서로 다른 회로의 콘센트까지 각각 닿게 할 수 있는지 판정한다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 완전 탐색, 기하
정답자
아직 제출이 없습니다

문제

만능 수리공 Harry는 작업 위치에서 테이블 톱과 아크 용접기를 동시에 사용하려고 한다. 두 기기 모두 많은 전류를 소모하므로, 서로 다른 두 전기 회로의 콘센트에 각각 꽂아야 한다. 작업장에는 여러 개의 콘센트가 있고, 각 콘센트는 여러 회로 중 하나에 연결되어 있다. Harry는 길이가 제각각인 연장 코드 여러 개를 가지고 있다.

연장 코드 몇 개를 서로 이어 붙여서, 톱을 한 콘센트에, 용접기를 다른 회로의 또 다른 콘센트에 동시에 연결할 수 있을까? 각 연결은 콘센트에서 작업 위치까지 일직선으로 늘어뜨린 코드들의 사슬이며, 하나의 코드를 두 연결에 동시에 쓸 수는 없다. 어떤 콘센트에 연결하려면, 그 연결에 배정한 코드들의 총 길이가 콘센트에서 작업 위치까지의 직선거리 이상이어야 한다.

입력

첫 번째 줄에 네 수 xx, yy, nn, mm이 주어진다. xx와 yy는 절댓값이 2 0002\,000 이하이고 소수점 아래 한 자리로 정확히 주어지는 실수로, Harry의 작업 위치 좌표이다. nn(1≤n≤1001 \le n \le 100)은 연장 코드의 개수, mm(1≤m≤1001 \le m \le 100)은 콘센트의 개수이다.

이어지는 nn개의 줄에는 각각 연장 코드 하나의 길이가 주어지며, 500500 미만의 양의 정수이다.

그다음 mm개의 줄에는 각각 세 값 aa, bb, cc가 주어진다. aa와 bb는 절댓값이 2 0002\,000 이하이고 소수점 아래 한 자리로 정확히 주어지는 실수로 콘센트의 좌표이며, cc(1≤c≤10 0001 \le c \le 10\,000)는 그 콘센트가 연결된 회로 번호이다.

바닥에는 장애물이 없으므로, 어떤 콘센트에서든 작업 위치까지 코드 사슬을 일직선으로 늘어뜨릴 수 있다.

출력

Harry가 톱과 용접기를 서로 다른 두 회로의 콘센트에 동시에 연결할 수 있으면 Harry can plug in his equipment.를 출력한다. 그렇지 않으면 Harry is helpless.를 출력한다.

예제2

  1. 예제 1

    입력
    100.0 100.0 3 3
    7
    8
    6
    100.0 106.0 1
    110.0 90.0 2
    89.0 111.0 3
    
    예상 출력
    Harry can plug in his equipment.
    
  2. 예제 2

    입력
    0.0 0.0 2 2
    10
    10
    1.0 0.0 5
    2.0 0.0 5
    
    예상 출력
    Harry is helpless.