Assume you are participating in a big project that deals with points in a two-dimensional plain. You are given the following structure definitions for points and segments that you should use and not modify:
struct point2D
{
int x;
int y;
};
struct segment2D
{
point2D p1;
point2D p2;
};
A point, therefore, is given by its (x,y)-coordinates.
A segment is a part of a straight line through two points p1 and p2. Assume several segments are stored in a text file. Each segment is encoded by a pair of its endpoints p1=(x1, y1) and p2=(x2, y2). The coordinates of these endpoints are in one text line in following format:
x1 y1 x2 y2
For example, if your file contains coordinates of 4 line segments, the file format is as follows:
-5 10 7 119
16 50 0 70
-5 10 0 70
16 50 7 119
The segments in the file are mixed up, but it is known that they form a polygon if you put them in a proper order. Your task is to figure out this order. More exactly, you must do the following:
* Design a class Polygon with a private variable head. This variable should be the head of a linked list containing the structures of type segment2D. The class has to have a public method sort specified below.
* The sort method of class Polygon should sort the segments in the linked list so that any two consecutive segments with numbers i and i+1 in the sorted list satisfy the following condition: the second endpoint of segment number i is the same as the first endpoint of segment number i+1. Moreover, the first endpoint of the first segment must be the same as the second endpoint of the last one.
* Create an instance of the class Polygon and read the segments from file into the linked list whose head pointer is head.
* Traverse the sorted linked list of segments from head to tail and output the coordinates of the segment endpoints to the screen, one line per segment.
For example, the above segment coordinates should be stored in the sorted linked list and output to the screen as follows:
-5 10 7 119
7 119 16 50
16 50 0 70
0 70 -5 10
Note that sometimes you might need to swap the points p1 and p2 in some segments.
Create your own data file test.dat containing endpoints of at least 10 segments (make sure that they really form a polygon and are mixed up, so that the program indeed has to do some work).