Edgar Mine

시간 제한3초메모리 제한2048 MB

요약
위치 E와 높이 H에 있는 전구가 샤프트의 한 점에 주는 빛은 L/(4π((수평 거리)²+H²))이다. 모든 점이 한 전구로부터 W lux 이상을 받도록 켤 전구의 최소 개수를 구한다.
난이도

보통10점 중 7점

유형
그리디, 구간, 정렬, 수학
정답자
아직 제출이 없습니다

문제

The year is 1894. Mines has just acquired the Edgar Mine in Idaho Springs, Colorado and it's your job as the mine foreman to see what Mines has just purchased.

While exploring the mine, you notice that there are a few different strands of light bulbs all hanging at different heights from the ceiling of the mine shaft, and all of the lights are on, which is rather blinding (and wasteful). Electricity prices at the mine are extremely high due to the remote location.

The previous electrical engineer for the mine has diagrams that provide the exact height from the floor (in meters) and luminosity of each light bulb (in lumens). The brightness of a light bulb BB can be calculated using the inverse-square law: \[ B = \frac{L}{4 \pi D^2} \] where,

  • L=the luminosity (in lumens)L=\text{the luminosity (in lumens)}, and
  • D=the distance from the bulb (in meters)D = \text{the distance from the bulb (in meters)}.

One lumen per square meter is known as a lux.

Safety regulations require that each point along the mine is lit to a minimum of WW lux by a single light bulb. If a point is lit to a total of WW lux by two separate light bulbs, but neither light bulb would light that point to at least WW lux by itself, the regulation has not been met. Can you determine the minimum number of light bulbs that must be turned on to follow the regulation?

If a light bulb lights up the floor of the shaft directly below it with XX lux, you can assume that it lights up the entire width of the shaft floor with XX lux (i.e. no need to consider the width of the shaft). You are guaranteed that you will be able to fulfill the safety regulation with some combination of bulbs.

입력

The first line of input contains three space-separated integers: the length of the shaft (in meters), 1≤S≤1061 \leq S \leq 10^6, the number of light bulbs 1≤N≤1061 \leq N \leq 10^6 and the required minimum brightness (in lux) 1≤W≤1,0001 \leq W \leq 1\\,000. Each of the next NN lines contains three space-separated values containing information pertaining to the NthN^{th} bulb: the distance (an integer in meters) of the bulb from the shaft entrance 0≤E≤S0 \leq E \leq S, the height (a float in meters) of the bulb from the floor of the shaft 0≤H≤1000 \leq H \leq 100, and the luminosity (an integer in lumens) 0≤L≤1060 \leq L \leq 10^6.

출력

The first (and only) line of output is the minimum number of light bulbs you can turn on to fulfill the safety regulation.

예제2

  1. 예제 1

    입력
    10 10 50
2 0.5 3000
4 0.5 3000
6 0.5 3000
8 0.5 3000
9 1 2000
1 2 4000
2 4 5000
4 1.25 4000
8 3 10000
10 5 10000
    예상 출력
    3

  2. 예제 2

    입력
    10 11 50
2 0.5 3000
4 0.5 3000
6 0.5 3000
8 0.5 3000
9 1 2000
1 2 4000
2 4 5000
4 1.25 4000
8 3 10000
10 5 10000
9 0.5 75000
    예상 출력
    1