## AtCoder Regular Contest 173B - Make Many Triangles

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 原題解法

只要任三個點都不在線上，那答案就是 $\lfloor n/3 \rfloor$。

我們發現如果不要有 $2/3$ 個點出現在同一條直線上，那答案還是一樣，因為我們可以用剩下的點來組成 $\lfloor n/3 \rfloor$ 個三角形。

如果超過的話就會影響答案，最直接的還是把同線上的兩兩一組，然後選一個不在線上的。

可以窮舉每兩個點當線，然後枚舉其他點，是 $O(N^3)$，足以通過。

其實似乎也有方法可以用處理斜率的方式降到約 $O(N^2 log N)$ 之類的，但在這題可能不會比較快。

### bonus

同原題，但改變 $N$ 的限制， $N \leq 10^5$。

### bonus 解法

如果用上述的方法應該是無法在時限內通過。

那我們觀察一個性質，我們要找的是最多點的線 $L$，題目要找的要線上有 $> \lfloor \frac{2n}{3}\rfloor$ 點才有用，所以如果這個 $L$ 上根本沒那麼多點，那答案勢必還是 $\lfloor n/3 \rfloor$，那我們可以改變策略，前面窮舉兩個點當線的步驟改用 random 選兩個相異的點。

證明 :

令 $L$ 上的點有 $a$ 個，要一次選到的機率是 $\frac{a}{n} \cdot \frac{a}{n} = (\frac{a}{n})^2$。

那一次選不到的機率是 $1 - (\frac{a}{n})^2$。

那連續 $b$ 次選不到的機率是 $P = (1 - (\frac{a}{n})^2)^b$。

因為 $a$ 越小 $P$ 會越大，取 $a = \frac{2n}{3}$。 (前面提到的性質 $a$ 不能小於這個數)

所以 $P = (\frac{5}{9})^b$

$b$ 如果只是 $1$ 感覺沒甚麼可信度，但是我們可以把 $b$ 弄大一點，值得注意的是當 $b = 50$，要都沒選到的機率已經低於 $10^{-12}$。

那這樣的時間複雜度是 $O(bN)$，取一個夠大的 $b$ 就可以。

### code

//Author : rickytsung
//Problem : ARC 173 B
//Date : 2024/3/12
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
using namespace std;
mt19937 rng(114514);
int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

int work(int n, pii* xy){
    int pt1 = rnd(0, n-1), cnt = 0;
    int pt2 = pt1;
    while((pt2 = rnd(0, n-1)) == pt1);
    i64 x1 = xy[pt1].f;
    i64 y1 = xy[pt1].s;
    i64 dx = xy[pt2].f - x1;
    i64 dy = xy[pt2].s - y1;
    for(int i = 0; i < n; i++){
        if(dx * (y1 - xy[i].s) == dy * (x1 - xy[i].f)){
            cnt ++;
        }
    }
    return cnt;
}

int main() {
    IOS;
    int n;
    cin >> n;
    int ans = n/3;
    pii xy[n];
    for(int i = 0; i < n; i++){
       cin >> xy[i].f >> xy[i].s;
    }
    for(int i = 0; i < 50; i++){
        ans = min(ans, n - work(n, xy));
    }
    cout << ans;
}