This repository aims to solve and create new problems from different spheres of coding. A path to help students to get access to solutions and discuss their doubts.
You are given a strictly convex polygon with N
vertices (numbered 1
through N
). For each valid i
, the coordinates of the i
-th vertex are (Xi,Yi)
. You may perform the following operation any number of times (including zero):
Consider a parent polygon. Initially, this is the polygon you are given.
Draw one of its child polygons ― a simple non-degenerate polygon such that each of its sides is a chord of the parent polygon (it cannot be a side of the parent polygon). The operation cannot be performed if the parent polygon does not have any child polygons.
The child polygon which you drew becomes the new parent polygon.
Your goal is to draw as many sides of polygons in total as possible (including the polygon given at the start). Find this maximum total number of sides
Enter link to the question(if question belongs to any online platform) -
rajatjha28
commented
2 years ago
Enter your question -
You are given a strictly convex polygon with N vertices (numbered 1 through N ). For each valid i , the coordinates of the i -th vertex are (Xi,Yi) . You may perform the following operation any number of times (including zero):
Consider a parent polygon. Initially, this is the polygon you are given. Draw one of its child polygons ― a simple non-degenerate polygon such that each of its sides is a chord of the parent polygon (it cannot be a side of the parent polygon). The operation cannot be performed if the parent polygon does not have any child polygons. The child polygon which you drew becomes the new parent polygon. Your goal is to draw as many sides of polygons in total as possible (including the polygon given at the start). Find this maximum total number of sides
Enter link to the question(if question belongs to any online platform) -
https://www.codechef.com/problems/POLYREL
Tags for the question(eg - Array, Basic, Stack, etc.) -
Greedy, Geometry