CF1284E New Year and Castle Construction

发表于 | 阅读数

平面上有$ｎ$个点，问你存在多少组四个点围成的四边形包含一个点。

所有情况$nC_{n-1}^4$ ，考虑不存在的情况，即不再四边形里的情况。枚举包含的那个点$p$，对于一个四边形外的点一定有一个最上面的点和最下面的点。再枚举四边形中离他最下面的点$x$,即$xp$这条直线中，在其上面的点任意选三个就可$x$组成四边形（可以想象最其中斜率（极角排序之后的点)最大)。

  • 这一个步骤可以用极角排序，用双指针维护这个可行区间。
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
typedef long double lb;
const int N = 3e3 + 10;
const int mod = 1e9 + 7;
const lb pi = acos(-1.0L);
struct point
{
    lb x, y;
    point operator-(point p) { return (point){x - p.x, y - p.y}; };
    point operator+(point p) { return (point){x + p.x, y + p.y}; };
    lb dis() { return sqrt(x * x + y * y); }
    lb cross(point p2) { return x * p2.y - y * p2.x; }
} p[N], s[N];
int n;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%Lf%Lf", &p[i].x, &p[i].y);
    ll res = 1ll * n * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 24;
    for (int i = 1; i <= n; i++)
    {
        vector<lb> ang;
        for (int j = 1; j <= n; j++)
            if (i != j)
                ang.push_back(atan2((p[j] - p[i]).y, (p[j] - p[i]).x));
        sort(ang.begin(), ang.end());
        int siz = n - 1, j = 0;
        for (int t = 0; t < siz; t++)
        {
            while (j < t + siz)
            {
                lb f = ang[j % siz] - ang[t];
                if (f < 0)
                    f += 2 * pi;
                if (f < pi)
                    j++;
                else
                    break;
            }
            ll p = j - t - 1;
            res -= 1ll * p * (p - 1) * (p - 2) / 6;
        }
    }
    printf("%lld\n", res);
}