2020安徽程式設計省賽 I美麗幾何

I 美麗幾何

在平面上有 n n n個點，初始每個點的美麗值都為 0 0 0，任意選擇兩個點組成一條直線，對于每一條直線，如果存在一個點，這個點到這條直線的距離小于其他 n ? 3 n-3 n?3個點到這條直線的距離，那么我們把這個點的美麗值加 1 1 1，為了簡化輸出，我們只需要輸出所有點的美麗值的異或值，保證三點不共線，

分析

為了形象的展示本題的需求，我們把所有的點放在一個坐標系中，并按照縱坐標從小到大的順序標定序號，(后面會解釋為什么要按照該順序標號)

圖 I ? 1 在 坐 標 系 中 點 的 排 序 圖I-1 \ \ \ \ 在坐標系中點的排序 圖I?1 在坐標系中點的排序

根據美麗值的定義：對于每一條直線，如果存在一個點，這個點到這條直線的距離小于其他點到這條直線的距離，那么我們把這個點的美麗值加一

求解所有的點的美麗值，即對于每一條直線，尋找距離其最近的一個點(若有多個點到直線距離相同則全部不計)，

想要完成上述程序，最樸素的思想是，先用 O ( n 2 ) O(n^2) O(n2)的時間復雜度列舉出所有的直線，然后再用 O ( n ) O(n) O(n)的時間復雜度列舉每個點到直線的距離，最后求出所有點的美麗值并輸出異或的結果，這樣的演算法時間復雜度恒為 O ( n 3 ) O(n^3) O(n3)，顯然不可取，在此基礎上，我們考慮本題的優化演算法，

和樸素演算法相同的地方在于點和線的結構體，我們用 p o i n t point point結構體存放點的坐標， l i n e line line結構體存放線的兩個端點的序號，以及直線的斜率，

簡化的突破口在于降低求解給定直線對應的距離其最短點的時間復雜度，因為很難找到某種方法能繞過列舉所有直線的程序來求解答案，對于給定的直線，如果能快速的找到其美麗點，那本題就迎刃而解了，

下圖介紹如何實作上述演算法：

圖 I ? 2 各 個 點 到 某 直 線 的 距 離 圖I-2 \ \ \ \ 各個點到某直線的距離 圖I?2 各個點到某直線的距離

從上圖可以看出，到直線 ① ⑥ ①⑥ ①⑥距離最近的點，可以通過比較綠色虛線的長度來求出，如果要比較所有綠色線段的長度，那時間復雜度仍然沒有降低，但如果將整張圖旋轉一下，那結果就清晰了很多，

圖 I ? 3 旋 轉 使 得 直 線 平 行 于 x 軸 的 情 形 圖I-3 \ \ \ \ 旋轉使得直線平行于x軸的情形 圖I?3 旋轉使得直線平行于x軸的情形

很顯然，在旋轉后的坐標系中，如果我們把直線 ① ⑥ ①⑥ ①⑥看作 x x x軸，那么離該直線最近的點即為縱坐標 ∣ y i ∣ |y_i| ∣yi?∣最小的點，換言之，我們可以把點按照某個斜率當成 x x x軸進行"從上到下"的排序，這樣當兩點共線的時候，用這兩個點的上下兩個點去更新答案就好了，這也解釋了我們最初為什么要按照縱坐標大小為點排序，

也就是說我們采用旋轉坐標系的方法，一開始按 y y y坐標排好序，然后維護時，每次當兩點共線后只要交換他們就能得到斜率轉過該事件點的序列，所以我們可以預處理出所有可行的斜率，當成事件點，不斷轉動坐標系更新答案就好，

自然，這樣的做法相對于樸素的三重回圈解法，時間復雜度有了很大的優化，考慮到維護旋轉坐標系時只需要常數級的操作次數，本題的期望時間復雜度為 O ( n 2 ) O(n^2) O(n2)

參考答案（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;
}