题解 CF1284E 【New Year and Castle Construction】

· · 题解

我看目前已有的题解，好像做法都和我的不同啊 QwQ。这里就介绍一下我的赛时做法吧（赛时的极角排序写挂了一直 WA on test 4...看半天硬是没看出来）

我的做法是基于以下这个结论的：

对于一个点 O，若其在四边形 ABCD 的内部，且 A、B、C、D 是按照以 O 为参照点顺时针方向排列，那么满足：OA \times OB < 0，OB \times OC < 0，OC \times OD < 0，OD \times OA < 0。

正确性？我只能说过于显然。知道叉积应该就能 Get 吧。

然后我们考虑这样一个计数方法：

  1. 枚举四边形的内部点 O
  2. 枚举钦定为四边形顶点的点 A
  3. 统计以 O 为起点，在 \overrightarrow{OA} 顺时针方向 180 \degree 内的向量个数 x，在 \overrightarrow{OA} 逆时针方向 180 \degree 内的向量个数 y
  4. 将答案加上 x \times \binom{y}{2}，再减去 \binom{y}{3}

为啥是对的呢？

首先我们先枚举一个内部的点 O 和四边形上的一个点 A。

考虑一个 naive 的想法：如果我们在 \overrightarrow{OA} 一侧选择一个点，另一侧选择两个点，这样的四边形就能满足条件。

但是事实上并不是所有的都满足条件。我们考虑下面这张图：

在我们枚举点 O 和点 C 时，B、C、D、E 组成的四边形我们会计算一次。但是这个四边形没有包括 O。

考虑这样不合法的四边形会有啥特征：会存在一个四边形上的点，在向量的顺时针方向 180\degree 内，其它三个点都在范围内！

也就是说，我们只需要在枚举每个向量的时候，减去这样的四边形个数就行了。

并且不难发现，这样的不合法的四边形只会恰好被加一次，减一次，所以正好抵消了。

然后再考虑合法的四边形：比如上图中的四边形 ACDE 就是一个合法的四边形。但是除了在枚举 C 的时候会被计算一次外，我们发现，在枚举 A 的时候也会被计算一次！

那么合法的四边形都只会被恰好计算两次么？

我们考虑这样一个事情：因为 \angle AOC + \angle COD + \angle DOE + \angle EOA = 360 \degree，且 \angle AOC < 180 \degree,\angle COD < 180 \degree,\angle DOE < 180 \degree,\angle EOA < 180 \degree，且任意三点不共线。那么一定不存在相邻两个角都为 90\degree。 然后可以分类讨论了：

一、三个锐/直角，一个钝角：

显然有两对角度数和小于 180\degree。再考虑锐角和钝角的和：如果小于 180\degree，则会出现：另外两个锐/直角度数和大于 180\degree 的超自然现象。

二、两个锐/直角，两个钝角：

同样使用上面的反证法，可以得到的确只有两对相邻的角的度数小于 180\degree。

那么我们就只需要将上面计数出来的答案除以二就得到了答案。

统计的时候如果暴力统计复杂度就是 O(n^3)，如果使用极角排序后 Two-Points （貌似也可以叫成尺取法）计算，复杂度为 O(n^2 \log n)

这个做法可以求出每个点的 f 值，貌似可以算成一种加强卡掉一些别的做法 QwQ

Code：(头文件请自行补充)

const int MAXN = 10000;

struct Node {
    int x, y;

    Node() {}
    Node(int x, int y):x(x), y(y) {}

    inline void rd() { x = read(), y = read(); }

    friend Node operator + (Node a, Node b) { return Node(a.x + b.x, a.y + b.y); }
    friend Node operator - (Node a, Node b) { return Node(a.x - b.x, a.y - b.y); }
    friend ll operator * (Node a, Node b) { return 1LL * a.x * b.y - 1LL * a.y * b.x; }
}a[MAXN], b[MAXN];

inline bool cmp(Node a, Node b) {
    // if(1LL * a.x * b.x == 0) return !a.x ? (a.y > 0 || b.x < 0) : !(b.y > 0 || a.x < 0);
    // else if(1LL * a.x * b.x < 0) return a.x > b.x;
    // 比赛的时候作死，硬要分象限讨论，然后上面一个 if 没写全当场暴毙
    return a * b < 0;
}

int main() {
    int n = read(); ll res = 0;
    for(int i = 1; i <= n; i++) a[i].rd();
    for(int i = 1; i <= n; i++) {
        int N = 0;
        for(int j = 1; j <= n; j++) if(i != j) b[++N] = a[j] - a[i];
        sort(b + 1, b + 1 + N, cmp);
        for(int j = 1; j <= N; j++) b[j + N] = b[j];
        for(int l = 1, r = 2; l <= N; l++) {
            while(r < l + N && b[l] * b[r] <= 0) ++r;
            int n1 = r - l - 1, n2 = N - n1 - 1;
            res += 1LL * n1 * n2 * (n1 - 1) / 2;
            res -= 1LL * n1 * (n1 - 1) * (n1 - 2) / 6;
        }
    }
    cout << res / 2 << endl;
    return 0;
} // 出乎意料的好写呢（但比赛的时候还是写挂了 QwQ