Spider Web
National Olympiad — Regional round (2015 season)
Submission name: www.cpp
Problem summary
Place n equally spaced points on a circle of radius R. Count unordered pairs whose straight chord has length at most d.
Input
R d n.
Output
The number of allowed chords.
Constraints
1 ≤ R ≤ 10000; 0 ≤ d ≤ 20000; 3 ≤ n ≤ 2000000000.
Worked example
Official sample; other valid outputs may exist.
Input
5 9 7
Output
14
Solution analysis
- Vertices separated by k edges along the shorter arc have chord length 2R sin(πk/n). This increases for 0 ≤ k ≤ floor(n/2), allowing binary search for the greatest permitted k.
- Each offset strictly below n/2 contributes n distinct unordered pairs. For even n the antipodal offset n/2 contributes only n/2 pairs, since each diameter is encountered twice. If d ≥ 2R, every pair is allowed.
- For R=5,d=9,n=7, offsets 1 and 2 qualify but offset 3 does not. Each contributes seven chords, giving 14.
Why it works
Binary search finds exactly the permitted offsets by monotonicity of sine on [0,π/2]. All unordered pairs have one unique shorter offset; counting n pairs at each non-antipodal offset and n/2 diameters counts every allowed pair once.
Complexity: O(log n) time and O(1) space.
Watch out. Use 64-bit counts; handle diameters separately. Long-double trigonometry avoids unnecessary loss of precision.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Binary search finds exactly the permitted offsets by monotonicity of sine on [0,π/2]. All
// unordered pairs have one unique shorter offset; counting n pairs at each non-antipodal offset and
// n/2 diameters counts every allowed pair once.
#include<iostream>
#include<cmath>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long r,d,n;
cin>>r>>d>>n;
if(d>=2*r){
cout<<n*(n-1)/2<<'\n';
return 0;
}
long long low=0,high=n/2;
const long double pi=acosl(-1.0L);
while(low<high){
long long mid=(low+high+1)/2;
long double chord=2.0L*r*sinl(pi*mid/n);
if(chord<=d+1e-12L){
low=mid;
}
else{
high=mid-1;
}
}
cout<<n*low<<'\n';
}