Problem G. Glorious Stadium
Input file: glorious.in
Output file: standard output
Balloon Color: Orange
A lot of people want to attend the World Cup, so we would like to construct a glorious stadium using the
following algorithm:
1. Construct 1st layer of the stadium by building a fence shaped like a regular polygon P1 with K
sides and its in-circle C1 (with radius R) is the field of the stadium.
2. Construct 2nd layer of the stadium by building a fence shaped like a regular polygon P2 with K
sides and its in-circle C2, such that C2 is the circumcircle of P1, so it surrounds the layer 1.
3. Construct 3rd layer of the stadium by building a fence shaped like a regular polygon P3 with K
sides and its in-circle C3, such that C3 is the circumcircle of P2, so it surrounds the layer 2.
Until · · ·
N. Construct n−th layer of the stadium by building a fence shaped like a regular polygon PN with K
sides and its in-circle CN , such that CN is the circumcircle of PN−1, so it surrounds the layer N −1.
For each layer of the stadium, the area of the polygon that is not included in its in-circle tells us the
amount of the people who can stay to cheer for the teams (because this is the only place they can sit).
We would like to calculate the sum of cheerers areas of all the N layers of the glorious stadium, that is:
∑
N
i=1
Area(Pi \ Ci)
Page 9 of 16
ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest
Arab Academy for Science, Technology and Maritime Transport, 2017
Input
The first line of the input consists of a single integer 1 ≤ T ≤ 105
the number of test cases. Each test
case consists of one line containing 3 space separated integers N, R, K. N is the number of layers of
the stadium, R is the radius of the stadium C1 and K is the number of sides of the polygons; where
1 ≤ N ≤ 105
, 1 ≤ R ≤ 100, 3 ≤ K ≤ 2 · 104 and 5 · K ≥ N.
Output
For each test case output a single line displaying the case number and the area of the cheerers rounded
to exactly 5 decimal places. The output will be checked with a relative error.
Example
glorious.in standard output
3
3 10 3
2 10 4
5 100 6
Case 1: 4314.57552
Case 2: 257.52220
Case 3: 31096.23444
Note
• in-circle is the largest circle the will fit inside a polygon that touches every side.
• circumcircle is the circle that passes through each vertex of the regular polygon.
• The given figure is a demonstration of the first test case, where the radius of the smallest circle is
the given R, and the answer is the area of the grey parts.
• The formula P \ C denotes the area covered in P and not covered in C, as shown in the figure.
简单的计算几何题目；
推公式即可解决；
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 100005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-5
#define pll pair<ll,ll>
#define lson 2*x
#define rson 2*x+1
long long qupower(int a, int b) {
long long ans = 1;
while (b) {
if (b & 1)ans = ans * a;
b >>= 1;
a = a * a;
}
return ans;
}
inline int read() {
int an = 0, x = 1; char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') {
x = -1;
}
c = getchar();
}
while (c >= '0'&&c <= '9') {
an = an * 10 + c - '0'; c = getchar();
}
return an * x;
}
double n,r,k;
double sum;
int main() {
// ios::sync_with_stdio(false);
freopen("glorious.in","r",stdin);
int t;
cin>>t;
int cnt=0;
while(t--){
cnt++;
cin>>n>>r>>k;
sum=0.0;
double R;
while(n--){
double ans=0.0;
R=1.0*r/(sin(pi*(k-2)/k/2));
double a=2.0*sqrt(R*R-r*r);
sum+=1.0*k/2*r*a-pi*r*r;
// cout<<sum<<endl;
r=R*1.0;
}
cout<<"Case "<<cnt<<": ";
printf("%.10f\n",1.0*sum);
}
}