PROBLEM LINK:
Div-2 Contest
Author: catastrophic25
Idea: mihil2701
Tester: shikhar7s
Editorialist: catastrophic25
DIFFICULTY:
EASY
PREREQUISITES:
Geometry, Expected value.
PROBLEM:
You have a n sided regular polygon. New n sided regular polygons are recursively formed by using the mid points of the previous polygon. Now if a point is randomly chosen inside the first polygon, what is the expected no. of polygons it will be inside?
EXPLANATION:
Suppose the expected value of the number of polygons a randoms point will be inside (our answer) be x. Now, consider the figure above, we have the following two cases -
-
If randomly chosen point is inside the outermost polygon but outside the second outermost polygon - In this case, the expected value is equal to 1 as the point is inside of a single polygon.
-
If randomly chosen point is inside the second outer polygon - The expected value is equal to ratio of the area of the inner polygon to the area of the outermost polygon times the answer for outermost polygon. Suppose it is equal to y.
By, the rule of linearity of the expectation,
x = 1 + y.
Let A1 = Area of outermost polygon,
A2 = Area of second outermost polygon
L1 = Length of side of outermost polygon
L2 = Length of side of second outermost problem
Area of a regular polygon = A = \frac{(L^{2}\cdot n)}{4\cdot tan(\pi/n)}, where n is number of sides of regular polygon.
Now, {y = \frac{A2}{A1} \cdot x}
\frac{A2}{A1} = \frac{(L2)^{2}}{(L1)^{2}}
ALso, by applying sine law over the smaller traingle outside the second outermost polygon, we can find the ratio , \frac {L1}{L2} = \frac{1}{cos(\pi/n)}
\frac {A2}{A1} = \frac{(L2)^{2}}{(L1)^{2}} = cos^{2}(\pi/n)
y = cos^{2}(\pi/n) \cdot x
The proof is attached here.
x = 1 + cos^{2}(\pi /n) \cdot x
sin^{2}(\pi/n) \cdot x = 1
x = cosec^{2}(\pi/n) which is the required answer.
SOLUTIONS:
Setters's Solution
#include <bits/stdc++.h>
using namespace std;
#define ld long double
const long double PI = acos(-1);
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
ld ans = sin(PI/(n * 1.0));
ans *= ans;
ans = 1/ans;
cout << fixed << setprecision(7) << ans << endl;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mp(a,b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SEC
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
//primes for hashing 937, 1013
template<typename T, typename U> static inline void amin(T &x, U y)
{
if (y < x)
x = y;
}
template<typename T, typename U> static inline void amax(T &x, U y)
{
if (x < y)
x = y;
}
void shikhar7s(int cas)
{
int n;
cin>>n;
const long double pi = acos(-1);
long double f=pi*(n-2);
f/=2.0;
f/=n;
long double ans=1.0/(cos(f)*cos(f));
cout<<fixed<<setprecision(12)<<ans<<endl;
}
signed main()
{
fast;
//freopen("input.txt", "rt", stdin);
//freopen("output.txt", "wt", stdout);
int t=1;
cin>>t;
int cas=1;
while(cas<=t)
{
shikhar7s(cas);
cas++;
}
return 0;
}TIME COMPLEXITY:
O(1) per testcase