- Forum
- General C++ Programming
- Cutting polygon into traingles formula
Cutting polygon into traingles formula
Pages: 12
Problem Statement
Mr. Pippo wants to start a new pizza shop. Everything about his pizzas is unique — the recipe is unique, the taste is unique, and even the shape of pizzas is unique. Instead of having a round shape like every other pizza, Mr. Pippo makes his pizzas in polygon shapes. For example, he can make his pizzas in a triangular shape or in a pentagonal shape.
Before serving a pizza, Mr. Pippo cuts it into triangular pieces. However, there are different ways he can cut the pizza. For example, a pentagonal pizza can be cut in five different ways as shown in the following figure. Each day, Mr. Pippo chooses a particular shape which can only be cut in an odd number of ways. Note that all the five cuts in the figure happen to be rotationally symmetric, but each of them is considered distinct.
Different ways a pentagonal pizza can be cut
Figure: Different ways a pentagonal pizza can be cut
Your task in this problem is to determine the shape of the pizza. Given the number of ways the pizza can be cut, you have to determine how many sides the pizza has.
Further clarification regarding the ways a pizza can be cut is given below:
A pizza can only be cut by connecting two vertices,
Two cuts on the pizza cannot cross each other, and
For an n-polygon there would be exactly (n-3) cuts which divide the pizza into (n-2) pieces.
Input Format
There will be up to 100 lines given where each line represents one test case. For each test case, the number of ways the pizza can be cut will be given. The number will be always odd and can be up to 308 digits long. The input is finished when end-of-file is reached.
Output Format
For each test case, print on a single line the number of sides the pizza has.
Sample Input
1
5
Sample Output
3
5
Explanation
For the first line of input, there is only one way to "cut" the pizza if the pizza is a triangle. This one way consists of no cuts at all.
For the second line of input, if there are five ways to cut the pizza, the pizza must be a pentagon, as shown in the figure in the problem description.
Mr. Pippo wants to start a new pizza shop. Everything about his pizzas is unique — the recipe is unique, the taste is unique, and even the shape of pizzas is unique. Instead of having a round shape like every other pizza, Mr. Pippo makes his pizzas in polygon shapes. For example, he can make his pizzas in a triangular shape or in a pentagonal shape.
Before serving a pizza, Mr. Pippo cuts it into triangular pieces. However, there are different ways he can cut the pizza. For example, a pentagonal pizza can be cut in five different ways as shown in the following figure. Each day, Mr. Pippo chooses a particular shape which can only be cut in an odd number of ways. Note that all the five cuts in the figure happen to be rotationally symmetric, but each of them is considered distinct.
Different ways a pentagonal pizza can be cut
Figure: Different ways a pentagonal pizza can be cut
Your task in this problem is to determine the shape of the pizza. Given the number of ways the pizza can be cut, you have to determine how many sides the pizza has.
Further clarification regarding the ways a pizza can be cut is given below:
A pizza can only be cut by connecting two vertices,
Two cuts on the pizza cannot cross each other, and
For an n-polygon there would be exactly (n-3) cuts which divide the pizza into (n-2) pieces.
Input Format
There will be up to 100 lines given where each line represents one test case. For each test case, the number of ways the pizza can be cut will be given. The number will be always odd and can be up to 308 digits long. The input is finished when end-of-file is reached.
Output Format
For each test case, print on a single line the number of sides the pizza has.
Sample Input
1
5
Sample Output
3
5
Explanation
For the first line of input, there is only one way to "cut" the pizza if the pizza is a triangle. This one way consists of no cuts at all.
For the second line of input, if there are five ways to cut the pizza, the pizza must be a pentagon, as shown in the figure in the problem description.
Last edited on
| ki have a problem which i need to solve i have wrote a code but it's not really correct |
What makes you think it's not correct? Or do we have to guess?
do you see some pattern ? like
iterate through all vertices
this vertex look with vertex + 2 (not its neighbor)
verify it is not intersecting another segment from the segment list
if not add this new segment
++
there is faster algorithm but this gives you an idea.
iterate through all vertices
this vertex look with vertex + 2 (not its neighbor)
verify it is not intersecting another segment from the segment list
if not add this new segment
++
there is faster algorithm but this gives you an idea.
Will you please show me a code.
@cire i'm submitting it on online judge, its giving wrong answer
@cire i'm submitting it on online judge, its giving wrong answer
| @cire i'm submitting it on online judge, its giving wrong answer |
Did you test the code? Or did you just write it and hope for the best?
Let's do a quick test. We'll feed your code 3 and see what it outputs.
http://ideone.com/ZbAr7H
We can see from the image you posted earlier that the 3 pieces result from a 5-sided pizza. But, your code outputs 3. Can you trace the logic of the program and figure out why?
Post edited with the full problem statement, please help.
@cire my code gave me wrong answer, i only got accepted on the first test case.
i really need the answer.. please help me
@cire my code gave me wrong answer, i only got accepted on the first test case.
i really need the answer.. please help me
| cpluscoder123 wrote: |
|---|
| i really need the answer.. please help me |
| cire wrote: |
|---|
| can you trace the logic of the program and figure out why? |
You must be able to reason about your code. Giving you the answer will not help you. Think.
Last edited on
@cire , i'm really stupid in math and geometry.
its not a homework, i just need to solve it to learn some formulas and increase my math/geometry skills.
i wish you will help me.
Thank you :)
its not a homework, i just need to solve it to learn some formulas and increase my math/geometry skills.
i wish you will help me.
Thank you :)
| i just need to solve it to learn some formulas and increase my math/geometry skills. |
You won't be learning any formulas or increasing your math or geometry skills by solving this problem. On the other hand, you may increase your problem solving and reasoning skills if you'll take the time to work it out yourself.
well the sixth element that appears is
www.isima.fr/f4/projets2009/coatelen_falk.pd
it is in french but use a translator or search for delauney triangulation c++
look at the pseudocodes , you have your answer there.
www.isima.fr/f4/projets2009/coatelen_falk.pd
it is in french but use a translator or search for delauney triangulation c++
look at the pseudocodes , you have your answer there.
Last edited on
Try to solve the inverse problem: Given a polygon of n sides, in how many was may be cutted.
When you perform a cut the polygon divides into two with a smaller number of sides, so you may use a recursive approach.
You'll notice that the answer grows quite fast and reach > 300 digits quite soon. So you could precalculate all those values and store them in a table.
Then to solve the original problem simply search the input in your table.
When you perform a cut the polygon divides into two with a smaller number of sides, so you may use a recursive approach.
You'll notice that the answer grows quite fast and reach > 300 digits quite soon. So you could precalculate all those values and store them in a table.
Then to solve the original problem simply search the input in your table.
Pages: 12