Please solve this problem with c++ that can run within time limit. Sample Input 1 5 1 1 1 -1 0 0 -1 -1 -1 1 Sample Outpu
Posted: Thu May 05, 2022 12:54 pm
Please solve this problem with c++ that can run within time
limit.
Sample Input
1
5
1 1
1 -1
0 0
-1 -1
-1 1
Sample Output
4
-1 -1
1 -1
1 1
-1 1
Problem E Convex Hull Time limit: 2s Finding the convex hull of a set of points is an important problem that is often part of a larger problem. There are many algorithms for finding the convex hull. ● Since problems involving the convex hull sometimes appear in the ACM World Finals, it is a good idea for contestants to know some of these algorithms. Finding the convex hull of a set of points in the plane can be divided into two sub-tasks. First, given a set of points, find a subset of those points that, when joined with line segments, form a convex polygon that encloses all of the original points. Second, output the points of the convex hull in order, walking counter-clockwise around the polygon. In this problem, given a set of points, you are required to write a program to construct the convex hull.
Input Specification The first line of input contains a single integer, the number of test cases to follow. The first line of each test case contains a single integer 3 <= n <= 100000, the number of points. The following n lines of the test case each describe a point. Each of these lines contains two integers. The two integers specify the x- and y-coordinates of the point. The x- and y-coordinates of each point will be no less than -1000000000 and no greater than 1000000000. No point will appear more than once in the same test case. The points in a test case will never all lie on a line.
Output Specification For each test case, generate the following output. First, output a line containing a single integer m, the number of points on the convex hull. Next output m lines, each describing a point on the convex hull, in counter-clockwise order around the hull. Each of these lines should contain the x-coordinate of the point, followed by a space, followed by the y-coordinate of the point. Start with the point on the hull whose x-coordinate is minimal. If there are multiple such points, start with the one whose y-coordinate is minimal.
limit.
- Please Solve This Problem With C That Can Run Within Time Limit Sample Input 1 5 1 1 1 1 0 0 1 1 1 1 Sample Outpu 1 (258.46 KiB) Viewed 36 times
- Please Solve This Problem With C That Can Run Within Time Limit Sample Input 1 5 1 1 1 1 0 0 1 1 1 1 Sample Outpu 2 (55.14 KiB) Viewed 36 times
1
5
1 1
1 -1
0 0
-1 -1
-1 1
- Please Solve This Problem With C That Can Run Within Time Limit Sample Input 1 5 1 1 1 1 0 0 1 1 1 1 Sample Outpu 3 (55.13 KiB) Viewed 36 times
4
-1 -1
1 -1
1 1
-1 1
Problem E Convex Hull Time limit: 2s Finding the convex hull of a set of points is an important problem that is often part of a larger problem. There are many algorithms for finding the convex hull. ● Since problems involving the convex hull sometimes appear in the ACM World Finals, it is a good idea for contestants to know some of these algorithms. Finding the convex hull of a set of points in the plane can be divided into two sub-tasks. First, given a set of points, find a subset of those points that, when joined with line segments, form a convex polygon that encloses all of the original points. Second, output the points of the convex hull in order, walking counter-clockwise around the polygon. In this problem, given a set of points, you are required to write a program to construct the convex hull.
Input Specification The first line of input contains a single integer, the number of test cases to follow. The first line of each test case contains a single integer 3 <= n <= 100000, the number of points. The following n lines of the test case each describe a point. Each of these lines contains two integers. The two integers specify the x- and y-coordinates of the point. The x- and y-coordinates of each point will be no less than -1000000000 and no greater than 1000000000. No point will appear more than once in the same test case. The points in a test case will never all lie on a line.
Output Specification For each test case, generate the following output. First, output a line containing a single integer m, the number of points on the convex hull. Next output m lines, each describing a point on the convex hull, in counter-clockwise order around the hull. Each of these lines should contain the x-coordinate of the point, followed by a space, followed by the y-coordinate of the point. Start with the point on the hull whose x-coordinate is minimal. If there are multiple such points, start with the one whose y-coordinate is minimal.