本系列题目为 2020 年为计算机试验班 91 开设的 COMP350105 “算法设计与分析” 课程之期末实验题目。 本题目的规定与要求不代表课程实验中的要求，本题目的得分不代表实验得分，本题目的数据也不代表课程期末实验的测试方式。 而且在本 OJ 上的程序正确性、效率性要求往往高于课程得分要求，但代码可读性、程序思想要求却低于课程得分要求。本题目为大家提供严谨的测试，请各位酌情根据自己能力解答。
用分分治法编写一个求解凸包问题的算法，并测试算法的正确性。【注：凸包问题】给定平面上 nnn 个点，从中找出一个最小点集，使该点集所组成的凸多边形包围所有的 nnn 个点。
给定平面点集在二维笛卡尔坐标系上，并且对任意点 (x,y)(x,y)(x,y)，x,yx, yx,y 均为整数。
每次测试仅有一组数据
第一行包含一个整数 nnn, 表示待求点集的大小
第二行至第 n+1n + 1n+1 行，每行包含三个整数，分别表示 i,xi,yii, x_i, y_ii,xi,yi，其中 iii 为该点的编号，i=1,2,3,⋯ ,ni = 1, 2, 3, \cdots, ni=1,2,3,⋯,n，按 iii 从小到大输入
第一行包含一个整数 kkk, 表示待求点集凸包的大小
第二行至第 k+1k + 1k+1 行，每行包含三个整数，分别表示 t,xt,ytt, x_t, y_tt,xt,yt，其中 ttt 为凸包上点的编号，t≤nt \leq nt≤n，按 ttt 从小到大输出
输入样例 1
4 1 3 3 2 -1 0 3 0 0 4 0 -3
输出样例 1
3 1 3 3 2 -1 0 4 0 -3
1≤n≤2×1051 \leq n \leq 2\times 10^51≤n≤2×105
−109≤xi,yi≤109-10^9 \leq x_i, y_i \leq 10^9−109≤xi,yi≤109
保证没有任意三点在一条直线上