#P10590. Magnetic Attraction
Magnetic Attraction
Magnetic Attraction
In a vast field, there are N magnets scattered around. Each magnet is characterized by a 5-tuple \( (x,y,m,p,r) \), where \( x,y \) represent its coordinates, \( m \) is its mass, \( p \) is its magnetic force, and \( r \) is its attraction radius.
A magnet \( A \) can attract another magnet \( B \) if
\[ \sqrt{(x_B-x_0)^2+(y_B-y_0)^2}\leq r_A \quad \text{and} \quad m_B \leq p_A, \]where \( (x_0,y_0) \) is the fixed location where the collector stands.
Initially, you have your own magnet \( L \) located at \( (x_0,y_0) \) with parameters \( (m_L,p_L,r_L) \). Holding magnet \( L \) (and staying at \( (x_0,y_0) \)), every magnet that can be attracted by \( L \) will be pulled to \( (x_0,y_0) \). At any moment, you may choose any magnet from those you have collected (including \( L \)) to attract additional magnets.
Your task is to determine the maximum number of magnets that can be collected. The initial magnet \( L \) counts towards the total.
inputFormat
The input begins with a line containing six integers: \( N\; x_0\; y_0\; m_L\; p_L\; r_L \), where \( N \) is the number of magnets scattered in the field and \( (x_0,y_0) \) is the location where magnet \( L \) is placed. The parameters \( m_L, p_L, r_L \) are the mass, magnetic force, and attraction radius of magnet \( L \), respectively.
Each of the next \( N \) lines contains five integers: \( x\; y\; m\; p\; r \), representing the coordinates, mass, magnetic force, and attraction radius of a magnet.
outputFormat
Output a single integer, the maximum number of magnets that can be collected (including the initial magnet \( L \)).
sample
3 0 0 1 5 3
1 1 3 4 2
3 0 6 10 1
2 2 4 1 1
2