凸包

凸包

描述

给定n 个二维平面上的点，求他们的凸包。

输入

第一行包含一个正整数 n。

接下来 n 行，每行包含两个整数 x,y，表示一个点的坐标。

输

令所有在凸包极边上的点依次为 p1,p2,...,pm（序号），其中 m 表示点的个数，请输出以下整数：

(p1 × p2 × ... × pm × m) mod (n + 1)

样例 1 输入

样例 1 输

样例 1 解释

所以答案为(9 × 2 × 6 × 7 × 1 × 5) % (10 + 1) = 7

样例 2

请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。

限制

3 ≤ n ≤ 10^5

所有点的坐标均为范围(-10^5, 10^5)内的整数，且没有重合点。每个点在(-10^5, 10^5) × (- 10^5, 10^5)范围内均匀随机选取

极边上的所有点均被视作极点，故在输出时亦不得遗漏

时间：4 sec

空间：512 MB

代码

#include <bits/stdc++.h> using namespace std;

// ================= 代码实现开始 =================

typedef long long ll; const int N = 300005;

// 存储二维平面点struct ip {

int x, y, i;

ip(int x = 0, int y = 0) : x(x), y(y), i(0) { }

void ri(int _i) {

scanf("%d%d", &x, &y);

i = _i;

}

};

// iv表示一个向量类型，其存储方式和ip一样typedef ip iv;

// 先比较x轴再比较y轴，

bool operator < (const ip &a, const ip &b) {

return a.x == b.x ? a.y < b.y : a.x < b.x;

}

// 两点相减得到的向量

iv operator - (const ip &a, const ip &b) {

return iv(a.x - b.x, a.y - b.y);

}

// 计算a和b的叉积（外积）

ll operator ^ (const iv &a, const iv &b) {

return (ll)a.x * b.y - (ll)a.y * b.x;

}

// 计算二维点数组a的凸包，将凸包放入b数组中，下标均从0开始

// a, b：如上

// n：表示a中元素个数

// 返回凸包元素个数

int convex(ip *a, ip *b, int n) {

//升序排序

sort(a, a + n);

int m = 0;

//求下凸壳

for (int i = 0; i < n; ++i) {

for (; m > 1 && ((b[m - 1] - b[m - 2]) ^ (a[i] - b[m - 2])) < 0; --m);

b[m++] = a[i];

}

//求上凸壳

for (int i = n - 2, t = m; i >= 0; --i) {

for (; m > t && ((b[m - 1] - b[m - 2]) ^ (a[i] - b[m - 2])) < 0; --m);

b[m++] = a[i];

}

return m - 1;

}

// ================= 代码实现结束 =================

ip a[N], b[N];

int main() {

    int n;

    scanf("%d", &n);

    for (int i = 0; i < n; ++i)

        a[i].ri(i + 1);

    int m = convex(a, b, n), ans = m;

    for (int i = 0; i < m; ++i)

        ans = ((ll)ans * b[i].i) % (n + 1);

    printf("%d\n", ans);

    return 0;

}