You are given a circle with k points on the outline, placed such that the distance between any two adjacent points is equal. The points are enumerated from 1 to k in clockwise manner. Given two points A and B, find the number of points C, such that angle ACB is obtuse.
QUICK EXPLANATION:
The fact is that all the points C located in one half-plane from line AB have equal angle ACB. So, we have to find the number of points between A and B on the circle. We can do it in O(1), so the total complexity is O(T).
EXPLANATION:
Lets split the points into two groups: located in one half-plane from line AB and in the other. The smallest group will be the answer — all the angles there would be obtuse. As we know, the angle, which leans on the diameter of the circle, is right angle. So we also have to check if AB is diameter, then the answer is 0.
The most simple solution is to transform the problem to the problem, when A = 1 and 2 \le B \le \lfloor{\frac{k}{2}}\rfloor + 1. Now the answer is 0, if B = \frac{k}{2} + 1, and B - 2 otherwise.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
@baap_42 dont go for finding 360/k , i also did the same and got wrong , because if k = 10^9 ,then 360/k will be very small and cant compare high precision values with low ones
I understood the explanation and had done the same but still i was getting the wrong answer. Can anyone please check my solution and help me with this. I would be really grateful to him/her. The link to my code is : CodeChef: Practical coding for everyone
@hloya_ygrt Doesn’t this case of AB being the diameter only apply for even number of candles (i.e., polygon’s with even number of sides). For odd numbered candles it don’t pass through the diameter at all for any value of A and B.
According to your solution, for k,A, B having 5, 1, 3 shouldn’t have any C because according to your formula it will form 90 degree for any C but the answer is 1. (1, 2 ,3) since 1,3 doesn’t pass through the diameter.
Don’t go for k/2. Got WA everytime.
You can try making a=1 and b as per input. Then calculate b-a-1 and also calculate counter clockwise subtraction i.e. k-(b-a-1)-2. Here two is to remove a and b candles.
example. k=8 a=1 b=6. Here b-a-1=4 but the actual answer is 2 as counter clockwise it will be 8-4-2=2.
The above statements mean to calculate the least difference between both candles in both directions and select the minimum, if both are same ans=0 as they are diametrically opposite.
@nikmul19 This is the exact same logic I went with, but its showing my submission as wrong. And please tell me what do you think about my argument on odd number of candles?
Here is my code that i submitted [CodeChef: Practical coding for everyone].
I understood the logic behind the problem and applied it during contest…But I am not getting where my solution is going wrong…Someone please check my solution link : https://www.codechef.com/viewsolution/15056224
