ICM0003 (Infinite polygons) - Editorial

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 -

  1. 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.

  2. 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

2 Likes

Nice problem

This was actually, simple if you knew a fairly good amount of trigo.
And another thing about maintaing precision in this problem, it is actually beneficial to use \pi upto 150 places and also instead of squaring \frac{1}{\sin{\frac{\pi}{n}}}, we can calculate \frac{2}{1 + \cos{\frac{2\pi}{n}}} and better our precision. I got 2 WA’s after which I did this, so it should be beneficial.

3 Likes

liked setters solution simple and easy