# CG2017 PA1-1 Convex Hull (凸包)

### Description (描述)

After learning Chapter 1, you must have mastered the convex hull very well. Yes, convex hull is at the kernel of computational geometry and serves as a fundamental geometric structure. That’s why you are asked to implement such an algorithm as your first programming assignments.

Specifically, given a set of points in the plane, please construct the convex hull and output an encoded description of all the extreme points.

### Input (输入)

The first line is an integer n > 0, i.e., the total number of input points.

The k-th of the following n lines gives the k-th point:

pk = (xk, yk), k = 1, 2, …, n

Both xk and yk here are integers and they are delimited by a space.

pk = (xk, yk), k = 1, 2, …, n

### Output (输出)

Let { s1, s2, …, sh } be the indices of all the extreme points, h ≤ n. Output the following integer as your solution:

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

### Sample Input (输入样例)


10
7 9
-8 -1
-3 -1
1 4
-3 9
6 -4
7 5
6 6
-6 10
0 8


### Sample Output (输出样例)


7   // ( 9 x 2 x 6 x 7 x 1 x 5 ) % (10 + 1)


### Limitation (限制)

• 3 ≤ n ≤ 10^5
• Each coordinate of the points is an integer from (-10^5, 10^5). There are no duplicated points. Each point is selected uniformly randomly in (-10^5, 10^5) x (-10^5, 10^5).
• All points on extreme edges are regarded as extreme points and hence should be included in your solution.
• Time Limit: 2 sec
• Space Limit: 512 MB
• 3 ≤ n ≤ 10^5
• 所有点的坐标均为范围(-10^5, 10^5)内的整数，且没有重合点。每个点在(-10^5, 10^5) x (-10^5, 10^5)范围内均匀随机选取
• 极边上的所有点均被视作极点，故在输出时亦不得遗漏
• 时间限制：2 sec
• 空间限制：512 MB

### Hint (提示)

Use the CH algorithms presented in the lectures.

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 #include #include #include #include using namespace std; struct point {     long long x, y, id;     point() :x(0), y(0) {}     point(long long x, long long y) :x(x), y(y) {}     bool operator ==(const point& p) const {         return x == p.x && y == p.y;     } }PP; //PP: Polar Point vector points; long long area2(point p, point q, point s) {     /*     |p.x p.y 1|     |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)     |s.x s.y 1|     */     return p.x * q.y - s.x * q.y         + q.x * s.y - q.x * p.y         + s.x * p.y - p.x * s.y; } bool toLeftTest(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) > 0; } bool toLeftTest2(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) >= 0; } bool cmp(const point& p1, const point& p2) { // Sort according to polar angle     return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2); } point LTL(vector& points) { //Lowest then leftmost     point ltl = points[0];     for (int i = 1; i < points.size(); i++) {         if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)             ltl = points[i];     }     return ltl; } vector grahamScan() {     PP = LTL(points);     sort(points.begin(), points.end(), cmp);     vector S, T;     S.push_back(points[0]); S.push_back(points[1]);     for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);     while (!T.empty()) {         if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {             S.push_back(T[T.size() - 1]);             T.pop_back();         }         else S.pop_back();     }     return S; } int main() {     ios::sync_with_stdio(false);     long long n;     cin >> n;     for (int i = 1; i <= n; i++) {         point tmp;         cin >> tmp.x >> tmp.y;         tmp.id = i;         points.push_back(tmp);     }     vector result;     if (points.size() > 2)result = grahamScan();     else result = points;     long long res = 1;     for (int i = 0; i < result.size(); i++) {         //cout << result[i].id << endl;//debug         res = ((res % (n + 1)) * (result[i].id % (n + 1))) % (n + 1);     }     res = ((res % (n + 1)) * (result.size() % (n + 1))) % (n + 1);     cout << res; }