2020安徽省大学生程序设计大赛题解——I 美丽几何

2020安徽省大学生程序设计大赛题解——I 美丽几何

I 美丽几何

在平面上有n个点，初始每个点的美丽值都为0，任意选择两个点组成一条直线，对于每一条直线，如果存在一个点，这个点到这条直线的距离小于其他n-3个点到这条直线的距离，那么我们把这个点的美丽值加1。为了简化输出，我们只需要输出所有点的美丽值的异或值，保证三点不共线。

题目

标签

计算几何，旋转坐标系，桶

分析

为了形象的展示本题的需求，我们把所有的点放在一个坐标系中，并按照纵坐标从小到大的顺序标定序号。(后面会解释为什么要按照该顺序标号)

$$图I-1在坐标系中点的排序$$

根据美丽值的定义：对于每一条直线，如果存在一个点，这个点到这条直线的距离小于其他点到这条直线的距离，那么我们把这个点的美丽值加一

求解所有的点的美丽值，即对于每一条直线，寻找距离其最近的一个点(若有多个点到直线距离相同则全部不计)。

想要完成上述过程，最朴素的思想是，先用$O(n^2)$的时间复杂度枚举出所有的直线，然后再用$O(n)$的时间复杂度枚举每个点到直线的距离，最后求出所有点的美丽值并输出异或的结果。这样的算法时间复杂度恒为$O(n^3)$，显然不可取。在此基础上，我们考虑本题的优化算法。

和朴素算法相同的地方在于点和线的结构体，我们用$point$结构体存放点的坐标，$line$结构体存放线的两个端点的序号，以及直线的斜率。

简化的突破口在于降低求解给定直线对应的距离其最短点的时间复杂度，因为很难找到某种方法能绕过枚举所有直线的过程来求解答案。对于给定的直线，如果能快速的找到其美丽点，那本题就迎刃而解了。

下图介绍如何实现上述算法：

$$图I-2各个点到某直线的距离$$

从上图可以看出，到直线$①⑥$距离最近的点，可以通过比较绿色虚线的长度来求出，如果要比较所有绿色线段的长度，那时间复杂度仍然没有降低。但如果将整张图旋转一下，那结果就清晰了很多。

$$图I-3旋转使得直线平行于x轴的情形$$

很显然，在旋转后的坐标系中，如果我们把直线$①⑥$看作$x$轴，那么离该直线最近的点即为纵坐标$|y_i|$最小的点。换言之，我们可以把点按照某个斜率当成$x$轴进行"从上到下"的排序。这样当两点共线的时候，用这两个点的上下两个点去更新答案就好了，这也解释了我们最初为什么要按照纵坐标大小为点排序。

也就是说我们采用旋转坐标系的方法，一开始按$y$坐标排好序，然后维护时，每次当两点共线后只要交换他们就能得到斜率转过该事件点的序列。所以我们可以预处理出所有可行的斜率，当成事件点，不断转动坐标系更新答案就好。

自然，这样的做法相对于朴素的三重循环解法，时间复杂度有了很大的优化，考虑到维护旋转坐标系时只需要常数级的操作次数，本题的期望时间复杂度为$O(n^2)$

参考答案（C++）

//Using C++11
#include<bits/stdc++.h>
using namespace std;
constexpr auto maxn = 2005;
int n;

struct point {
    int x, y;
    point() {}
    point(int x, int y) {
        this->x = x;
        this->y = y;
    }
    point operator - (const point& b) const
    {
        return point(x - b.x, y - b.y);
    }
    int operator ^ (const point& b) const
    {
        return x * b.y - b.x * y;
    }
};
bool cmp_point(point a, point b) {
    return a.y < b.y;
}
point a[maxn];

struct line {
    int x_id, y_id;
    double polar;
    line() {}
    line(int x, int y) {
        x_id = x;
        y_id = y;
        polar = atan2(a[y].y - a[x].y, a[y].x - a[x].x);
    }
};
bool cmp_line(line a, line b) {
    return a.polar < b.polar;
}
vector<line> v;

int cal(int begin, int end1, int end2) {
    return abs((a[begin] - a[end1]) ^ (a[begin] - a[end2]));
}

int id[maxn];
int beauty[maxn];
int info[maxn];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    sort(a + 1, a + 1 + n, cmp_point);

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            v.push_back(line(i, j));
        }
        id[i] = info[i] = i;
    }
    sort(v.begin(), v.end(), cmp_line);

    for (line l : v) {
        int t1 = l.x_id;
        int t2 = l.y_id;
        if (id[t1] > id[t2]) {
            swap(t1, t2);
        }
        if (id[t1] > 1 && id[t2] < n) {
            if (cal(info[id[t1] - 1], t1, t2) == cal(info[id[t2] + 1], t1, t2));
            else if (cal(info[id[t1] - 1], t1, t2) < cal(info[id[t2] + 1], t1, t2))
                beauty[id[t1]]++;
            else beauty[id[t2]]++;
        }
        else if (id[t1] > 1) beauty[id[t1]]++;
        else if (id[t2] < n) beauty[id[t2]]++;
        swap(beauty[id[t1]], beauty[id[t2]]);
        swap(id[t1], id[t2]);
        info[id[t1]] = t1;
        info[id[t2]] = t2;
    }
    int ans = beauty[1];
    for (int i = 2; i <= n; i++) {
        ans ^= beauty[i];
    }
    cout << ans << endl;
    return 0;
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

p.s.这篇我师傅应同学之请在我们报告提交前就在CSDN上发表过
原文链接