A problem with connected points and determining geometry figures based on points' location analysis
- by StolePopov
In school we have a really hard problem, and still no one from the students has solved it yet. Take a look at the picture below:
http://d.imagehost.org/0422/mreza.gif
That's a kind of a network of connected points, which doesn't end and each point has its own number representing it. Let say the numbers are like this: 1-23-456-78910-etc. etc.. (You can't see the number 5 or 8,9... on the picture but they are there and their position is obvious, the point in middle of 4 and 6 is 5 and so on).
1 is connected to 2 and 3, 2 is connected to 1,3,5 and 4 etc.
The numbers 1-2-3 indicate they represent a triangle on the picture, but the numbers 1-4-6 do not because 4 is not directly connected with 6.
Let's look at 2-3-4-5, that's a parallelogram (you know why), but 4-6-7-9 is NOT a parallelogram because the in this problem there's a rule which says all the sides must be equal for all the figures - triangles and parallelograms.
Also there are hexagons, for ex. 4-5-7-9-13-12 is a hexagon - all sides must be equal here too.
12345 - that doesn't represent anything, so we ignore it.
I think i explained the problem well. The actual problem which is given to us by using an input of numbers like above to determine if that's a triangle/parallelogram/hexagon(according to the described rules).
For ex:
1 2 3 - triangle
11 13 24 26 -parallelogram
1 2 3 4 5 - nothing
11 23 13 25 - nothing
3 2 5 - triangle
I was reading computational geometry in order to solve this, but i gave up quickly, nothing seems to help here. One friend told me this site so i decided to give it a try.
If you have any ideas about how to solve this, please reply, you can use pseudo code or c++ whatever. Thank you very much.
