Question 4: Convex Polygon (Bonus 10%)

(the relation between k and n should be judged by the program. in the given n points, the program should be able to judge which points are vertices)

(C programming C programming C programming, please help me before 22th, Feb, 23:00)

You are given a list of points. You are asked to identify the subset of points constructing the convex polygon.

Your program should read the input from the file, and output the answer to another file. The first argument is the input file name, while the second argument is the output file name. Name your program as lab3-q4.c.

Hint: This question involves the techniques (i) sorting, (ii) stack and (iii) 2-d geometry.

Input file: First line, n 100, an integer indicating the number of points on the coordinate plane. Following n lines, each line consists of 2 integers, x y, indicates the coordinate of a point. You can safely assume that (0, 0) must be the first point. Besides (0, 0), the x-coordinate and y-coordinate are all positive.

Output file: k lines of points, each line consists of 2 integers, x y, which indicate a k-sided convex polygon. The first point must be (0, 0), and you should output the point in the anti-clockwise direction of the convex polygon. If points p1, p2, p3 are collinear and on the edge of convex polygon, you should only output the two vertices.

(the relation between k and n should be judged by the program. in the given n points, the program should be able to judge which points are vertices)

Sample Input:

4 00 1 10 55 10 1

Sample Output:

00 10 1 1 10

Question 4: Convex Polygon (Bonus 10%) You are given a list of points. You are asked to identify the subset of points constructing the convex polygon. Your program should read the input from the file, and output the answer to another file. The first argument is the input file name, while the second argument is the output file name. Name your program as "lab3-44.c". Hint: This question involves the techniques (i) sorting, (ii) stack and (iii) 2-d geometry. Input file: First line, ns 100, an integer indicating the number of points on the coordinate plane. Following n lines, each line consists of 2 integers, x y, indicates the coordinate of a point. You can safely assume that (0,0) must be the first point. Besides (0,0), the x-coordinate and y-coordinate are all positive. Output file: k lines of points, each line consists of 2 integers, xy, which indicate a k-sided convex polygon. The first point must be (0, 0), and you should output the point in the anti-clockwise direction of the convex polygon. If points p1, P2, P3 are collinear and on the edge of convex polygon, you should only output the two vertices. Sample Input: 4 1 10 5 5 10 1 Sample Output: 00 10 1 1 10