PROBLEM LINK:
DIFFICULTY:
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 Aand 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:
Let’s 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 a 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 into the problem, when
A = 1 and 2 ≤ B ≤ \lfloor \frac{k}{2} \rfloor + 1. Now the answer is 0, if B= \frac{k}{2} + 1, and B - 2 otherwise.
ALTERNATE EXPLANATION:
it was a simple maths problem, where you can simply check if |b-a|==n/2 (IF N IS EVEN)then it lies on the diameter, hence the answer will be always 0, read in lower classes that any triangle drawn with the diameter as the base will be 90 at the circumference.
If the points do not form a diameter then, for example, if I take k as 11 and A as 2 and B as 7 then there are two parts one which has(3,4,5,6) and the other has (8,9,10,11,1) hence the part with the lower value will be your answer since the part with higher values will form acute angles (basic maths).
Some basic maths will get you the formulae.
SOLUTIONS:
Solution
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
int n,a,b;
cin>>n>>a>>b;
if(a>b) swap(a,b);
if(n%2==0 && b-a == n/2){
printf("0\n");
continue;
}
int ans = min(b-a,n-b+a);
printf("%d\n",ans-1);
}
return 0;
}