시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Each second Martynas catches a glimpse of the sky through his telescope expecting to see a falling star. Every time he sees a falling star he makes a wish upon it.
Martynas believes that the more falling stars he will see while making a wish, the higher the probability the wish will come true.
Calculate the largest possible number of stars Martynas can see during a glimpse through his telescope.
The sky can be modelled as an endless plane. Martynas can see an area limited by a circle with center $(0, 0)$ and radius $R$.
Before opening his telescope Martynas checked the star chart:
Martynas can keep looking at the stars forever.
The first input line contains two numbers: the total amount of stars $N$ and the radius of the circle $R$.
Each of remaining $N$ lines contains $4$ integers each: $a_i$, $b_i$, $c_i$, $d_i$ describing the position of $i$’th star during the first and the second glimpse.
The first and the only output line should contain one integer – largest possible number of stars visible through the telescope.
번호 | 배점 | 제한 |
---|---|---|
1 | 23 | $-10\,000 ≤ R, a_i , b_i , c_i , d_i ≤ 10\,000$ and $b_i = d_i$ and $N ≤ 1\,000$ |
2 | 23 | $-10\,000 ≤ R, a_i , b_i , c_i , d_i ≤ 10\,000$ and $b_i = d_i$ |
3 | 15 | $-10\,000 ≤ R, a_i , b_i , c_i , d_i ≤ 10\,000$ and $N ≤ 1\,000$ |
4 | 32 | $-10\,000 ≤ R, a_i , b_i , c_i , d_i ≤ 10\,000$ |
5 | 7 | No additional constraints |
3 2 -5 0 -4 0 3 0 2 0 10 0 9 0
2
During the second and the third glimpse Martynas will see only the 2nd start. During the fourth, the fifth and the sixth glimpse he will see the 1st and the 2nd stars. When glancing the seventh and the eigth time he will see only the 1st star, and from the ninth to the thirteenth time he will only see the 3rd star.
2 1 -3 -2 -1 -1 -2 2 -1 1
2
Both stars are visible during the second glimpse.
2 2 3 0 5 0 -2 1 2 1
0
This time Martynas was unlucky. One star will fly through the telescope between the first and the second glimpse, the other – between the first and the second glimpses.
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2018/2019 > Final Round 2번