OBTTRNGL - Editorial

Author: Yuri Shilyaev
Editorialist: Yury Shilyaev

Easy

PREREQUISITES:

Simple geometry facts.

PROBLEM:

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.

RELATED PROBLEMS:

Codeforces 421 div2 - Mister B and Angle in Polygon

2 Likes

I got wrong answer during the contest but I do have the logic clear.Can you please help me understand why is my code failing? Thanks
https://www.codechef.com/viewsolution/15052445

https://www.codechef.com/viewsolution/15054629

Same logic. Works for a lot of test cases. But I am getting wrong answer. Please tell me where the mistake is.

@abhishekans21
I think itâ€™s because you need to convert (n/2) to floating type before you check. I was facing the same issue.

There is no need to calculate n/2 as that could lead to floating point comparison problems.
Hereâ€™s a solution without it.

I did and, it didnâ€™t work.

@abhishekans21 if n = 7 or 6 your n/2 will be same in second case and will give zero as output

@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

https://www.codechef.com/viewsolution/15057462
can any one help me in finding where my code is wrong , i am getting right ans for all test case but still its showing WA

This link has some very nice pictures to illustrate angles between 3 points on a circle:

https://www.mathsisfun.com/geometry/circle-theorems.html

â€¦ for those of us who didnâ€™t pay attention during geometry class in school.

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 : https://www.codechef.com/viewsolution/15053145

@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 [https://www.codechef.com/viewsolution/15063066].

1 Like

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

Can someone help me with my solution here please â€¦!
https://www.codechef.com/viewsolution/15132085

1 Like

@sangkv97 @habibkhan floating point creates a lot of problems in this question as @chin_nani pointed it out.
So better ignore it.

@sud96 your solution will give a negative answer if B<A. so you were wrong at that point.

Canâ€™t anyone make a good diagram so that it could be understood easily instead of writing long textual comments ?