This problem is about a very sad and very romantic story.
But it's also very fake, so please do not take it seriously and do not cry.
Vinkle was a kind-hearted boy. However, he didn't do well at school, nor was
he good at sports; in fact, he deemed that he excels in nothing.
For the whole span of his short life, he lacked sense of presence.
But there is one thing, just one, that he cares very much and would not let
go even when he left this world.
He fell deeply in love with this girl Elvink when he was alive. Though he never
dared speak it out to her, in his heart he had always wanted to say to the girl
some day: "I love you."
The fate is cruel, though.
That day never came and a terrible sickness took Vinkle's life.
Being reluctant to leave this world, Vinkle became a ghost, wandering in the
realm of human world in his after-life. He decided that he does not want to
leave any more regret, so even as a ghost, he decided to express his love to
Elvink. (.. Spooky.)
"I love you," the three words he had always dreamt to say.
Vinkle is determined never to back up this time.
One problem is, because his lack in sense of presence, he's a very transparent
ghost (unlike other ghosts who normally tend to be white), and Elvink would
not be able to see him even if he fly right through Elvink. So the first thing
Vinkle needs to do (before saying the important line) is to make himself
visible.
Therefore Vinkle came to the mad scientist N.K.Evil for help. After brief
elaboration to his awkward situation, N.K.Evil said that he could help.
"I invented a device called 'illusion duplicator', which might be able to help
you. There are a total of N duplicators, each installed at some fixed position
(xi,yi). Now suppose you are standing at a point, then duplicator 1 will copy
an illusion of you at the opposite side, with the duplicator itself as the
origin of symmetry. After that, the duplicator 2 will do the same to the
illusion created by duplicator 1 (thus creating a second illusion). This
continues so that each duplicator create a new illusion in symmetry to the
previous one, until duplicator N creates the last illusion and the whole
process ends."
"So how can this help? I don't understand!", said Vinkle.
"You are way too transparent to be visible. However, using this device we can
create lots of illusion of you at different positions. If you can stand at
some position so that many illusions overlap at the same place, then at that
point you might become visible! Or at least... barely visible.."
Given the position of the N duplicators, help Vinkle decides how many illusions
at most can overlap at a point, if Vinkle stands at optimal position.
Vinkle himself also counts as one illusion.
First line contains a number T indicating the number of testcases.
Each testcase consists of an integer N that represents the number of duplicator. Then follows N lines of pair of integers describing the coordinate of the duplicators in the same order they work.
T <= 100
N <= 100000
|xi|,|yi| <= 100000000
For each testcase, please output one line indicating in the best case, how many illusions (including Vinkle himself) could overlap at one place?
2 3 1 1 2 2 3 3 2 2 3 7 6
2 2
Migrated from old NTUJ.
kelvin
No. | Testdata Range | Score |
---|