set a polygon coordinates of their vertices along the bypass of its contour. It is required to indicate a set of non-cycle in the inner points of diagonals, breaking the polygon on triangles.
Login: The input.txt file,, in the first row of which the number N is recorded – the number of vertices of the polygon, then in n lines of a pair of integers – coordinates of the top of the polygon in the circuit bypass.
Restrictions: 4 ≤ N ≤ 200 ; Each coordinate from -5000 to 10,000 .
Exit: Output.txt file, in the first line of which there must be the number K indicating the required number of diagonals. In the following k, lines should be two natural numbers – the number of the initial and final vertex of the corresponding diagonal.
Additional limitations: diagonals must be lying strictly inside the polygon (all points are diagonal, except for the ends, are internal points of the polygon).
Example:
input.txt
5
eleven
2 5.
5 5.
5 1.
2 2.
Output.txt
2.
2 5.
3 5.
My decision:
-
The number of diagonals is equal (number of vertices – 3)
-
We connect all points from (2) to (the number of vertices – 2) with the last point; If the line between the connected and last point lies outside the polygon (the polygon is Neviply), then take the next point and connect
Its with some (what?) dots.
Help, please, all this is realized or tell me how to check the identity of a straight line (or point) polygon and which points to connect if the polygon is unspecified.
Answer 1, Authority 100%
- if the number of vertices & lt; = 3 Breakage completed
- Choose the first vertex as the current (N)
- If it is impossible to carry out a diagonal inside the polygon to the N + 2 point, then the following is the following, etc. By ring. I think you can prove that this cycle is not infinite.
- “Cut” a triangle from a polygon, the vertices becomes one less due to the exception of the vertex N + 1.
- go to clause 1
Probably convenient to use a connected list.
Definition is a diagonal inside a polygon.
We define in advance in what direction a polygon is set – by or counterclockwise. Further, if the triangle N n + 1 n + 2 costs in the opposite direction, then our diagonal is outside – not suitable.
Otherwise, another option is possible when the diagonal turns out to be outside in whole or in part by the fault of other internal angles, this is checked further.
For points N + 3 and N-1, it is necessary to check that these angles at these vertices are greater than the corresponding angles of the triangle. Those. The peak lies on the other side of the diagonal relative to the vertex N + 1, or the angle at the top is more unfolded. (See the picture for the vertex 2 angle 2-3-1 more than 2-3-4, or 4 and 2 are on one side of the diagonal of 3-1, so the diagonal 3-1 does not fit. For the top 8, it is with a vertex 6 On one side of the diagonal of 7-1, but the angle 7 is more deployed, so it does not interfere, the vertex is suitable.)
For the remaining parties, you need to check if they crossed this diagonal. (For example, in Figure, the side 6-7 crosses the diagonal 4-2. The intersection point of the straight line belongs to the segment.) There are no four parties to check: this is the side at the top and the neighboring to them.
Determination of the direction of bypass bypass
We carry out from one vertex A1 of the vector to all the remaining A1- & GT; A2, A1- & GT; A3, … A1- & GT; AN.
We consider the amount of N-1 vector works of adjacent vectors in order, we are transmitted only by the Z coordinate. This amount according to the module is equal to the double area of the figure, and the sign indicates the direction of bypass.
Optimization from @ant: In order to determine the direction of bypass by the polygon, it suffices to calculate the vector product of the parties incident with the lower left vertex (minimum x among the minimum Y). Do it in all vertices (i.e., consider the full area) there is no need.
Illustration of the cases considered in the algorithm.
ANSWER 2, AUTHORITY 11%
The classic solution algorithm for this task is to perform two steps
- Decomposition of the original polygon on monotonous polygons. This task is neatly solved by the algorithm of scanning direct.
- Triangulation of each monotone polygon. This is done by a simple triangulation algorithm.
Ultimately, the resulting algorithm will be much easier and more efficient than the “cutting of the ears” algorithm with a diagonal check in the polygon.