TIOJ 1747：[APIO '10] Signaling [Interactive]

TIOJ 1747：[APIO '10] Signaling [Interactive]

題目大意：給你 $n$ 個點，保證任三點不共線，任四點不共圓，可以挑三個點，畫出此三點外接圓，這個圓可以覆蓋若干個點，請你求出所有外接圓覆蓋點數的平均。

解法：挑四個點，這四個點必定組成凸四邊形或凹四邊形，令凸四邊形數量 $X$，凹四邊形數量 $Y$，則 $\text{all}=X + Y = C_4^n$。首先看凸四邊形，假設其為 $ABCD$，因為四點不共圓，所以兩組對角和中一定有一組大於 $180^\circ$，假設 $\angle DAC + \angle BCD > 180^\circ$，那 $DAC$ 的外接圓會包住 $B$，$BCD$ 的外接圓會包住 $A$，所以一個凸四邊形會貢獻 $2$ 個答案，再來看凹四邊形，假設在 $ABCD$ 裡 $A$ 是凹點，那 $BCD$ 的外接圓會包住 $A$，所以 $1$ 個凹四邊形會貢獻一個答案，所以最後的答案就是 $3 + \frac{2\times X + Y}{C_3^n}$。

再來我們觀察兩種四邊形裡有幾個角度是小於 $180^\circ$ 的，凸四邊形有 $4$ 個，凹四邊形有 $3$ 個 ($BCD,CDB,DBC$)，如果我們算出 $\text{sum}=4\times X + 3\times Y$，那就可以算出答案了。我們可以把 $n$ 個點各自當作原點，對其他點極角排序，之後可以枚舉其中一個邊，用雙指針找出最遠且與此邊角度小於 $180^\circ$ 的邊，如果中間有 $\text{cnt}$ 條邊，那會有 $\frac{(\text{cnt} - 1)\times (\text{cnt} - 2)}{2}$ 個角。最後 $X = \text{sum} - 3\times\text{all},Y = \text{all}-\text{X}$，$2\times X + Y=X+\text{all}=\text{sum}-2\times\text{all}$。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
#include "lib1747.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1505;

using T = pair<int, int>;

T operator - (T a, T b) {return T (a.F - b.F, a.S - b.S);}
ll operator * (T a, T b) {return 1ll * a.F * b.S - 1ll * a.S * b.F;}

int n, m;
ll all, sum;
T p[SIZE], a[SIZE];

void deal() {
    sort (a + 1, a + m + 1, [] (auto p1, auto p2) {
        bool t1 = (p1.F > 0 && p1.S >= 0) || (p1.F <= 0 && p1.S > 0);
        bool t2 = (p2.F > 0 && p2.S >= 0) || (p2.F <= 0 && p2.S > 0);
        return t1 != t2 ? t1 > t2 : p1 * p2 >= 0;
    });
    for (int i = 1, j = 1; i <= m; i++) {
        if (j == i) j = i == m ? 1 : i + 1;
        while (j != i && a[i] * a[j] > 0) j = j == m ? 1 : j + 1;
        int cnt = j - i;
        if (cnt <= 0) cnt += m;
        if (cnt > 2) sum += (cnt - 1) * (cnt - 2) / 2;
    }
}

void solve() {
    cin >> n;
    FOR (i, 1, n) cin >> p[i].F >> p[i].S;
    FOR (i, 1, n) {
        m = 0;
        FOR (j, 1, n) if (i != j) a[++m] = p[j] - p[i];
        deal();
    }
    all = 1ll * n * (n - 1) * (n - 2) * (n - 3) / 24;
    Report (p[1].F, 3 + 1.00 * (sum - 2 * all) / (1ll * n * (n - 1) * (n - 2) / 6));
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！