Approach for the question
https://www.codechef.com/MAY19B/problems/WTBTR
I just can't understand how to start the approach.Please help.I know it's a live contest so don't give direct code of the question.
You'll need
- pencil
- graph paper
- rule
Test case 1
3
0 0
0 1
0 -1
We should build roads described by equations y−x+0.5=0 and y−x−0.5=0.
1. Plot the three points 0,0 ; 0,1 and 0,-1 on the graph paper.
2. Draw the two lines given by y−x+0.5=0 and y−x−0.5=0
3. Work out WHY those lines are the satisfactory solution to the problem.
Then do the same for the other test case.
Then create some of your own test cases, until you understand how to solve the problem.
- pencil
- graph paper
- rule
Test case 1
3
0 0
0 1
0 -1
We should build roads described by equations y−x+0.5=0 and y−x−0.5=0.
1. Plot the three points 0,0 ; 0,1 and 0,-1 on the graph paper.
2. Draw the two lines given by y−x+0.5=0 and y−x−0.5=0
3. Work out WHY those lines are the satisfactory solution to the problem.
Then do the same for the other test case.
Then create some of your own test cases, until you understand how to solve the problem.
I am not getting the idea even after different test cases that is why I'm asking the doubt here.
Is there any algorithm for such questions
Is there any algorithm for such questions
Last edited on
some hints:
- rotate the plane so now the slope is 0, \infty (horizontal and vertical lines)
- think about the case where the answer is 0, ¿what happened there?
- ¿how would you solve for n=2? ¿and n=3?
- ¿what if you could construct n line segments and then remove one? ¿how will hhe rest adjust for the solution to be optimal?
> Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.
I highly doubt that, they probably do a diff against the answer file, they won't measure the error of your answer
(also, ¿that `or' means `and'?)
- rotate the plane so now the slope is 0, \infty (horizontal and vertical lines)
- think about the case where the answer is 0, ¿what happened there?
- ¿how would you solve for n=2? ¿and n=3?
- ¿what if you could construct n line segments and then remove one? ¿how will hhe rest adjust for the solution to be optimal?
> Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.
I highly doubt that, they probably do a diff against the answer file, they won't measure the error of your answer
(also, ¿that `or' means `and'?)
I'm getting partial marks as there are few WA in some test cases can you help.....and there is no TLE
I have got partial marks. What is the logic of getting All AC ? please help. I m stuck on this from many days.
Topic archived. No new replies allowed.