牛客多校day2B

题意

在二维平面上有N（2e3）个点，需要找到一个经过原点的圆，使得这个圆经过的点最多，保证给定的点不包含原点和重复点

思路

不用板子的良心计算几何。
首先有一个结论，任意两条线段的中垂线交点作为圆心，这个圆必过这两条线段的四个点，那思路就很简单了，因为必过原点，所以我们把原点和其他点连起来都求一遍中垂线，然后找出这些中垂线所有的交点，对于每个交点统计答案即可。
枚举所有的中垂线O(n^2)，每个交点用坐标存个map统计经过的线段的数量，再遍历求最值也是O(n^2)，故总时间复杂度O(n^2)，空间复杂度O(n^2)

AC代码

/*
 * Codeforces Contest
 * Au: Lost_Deviation
 */
#include <bits/stdc++.h>
#ifndef open_dbg_func
#define dbg(args...) (args)
#endif
using namespace std;
#define ll long long
#define bll unsigned long long
const int maxn = 1e5 + 7;
const double eps = 1e-6;
static auto x = []() {
    std::ios::sync_with_stdio(false); // turn off sync
    cin.tie(nullptr);                 // untie in/out streams
    return 0;
}();
vector<string> split(string str, const string &delimiters) {
    regex del(delimiters);
    vector<string> v(sregex_token_iterator(str.begin(), str.end(), del, -1),
                     sregex_token_iterator());
    return v;
}
struct T {
    int x, y;
};
int cmp(const T &a, const T &b) {
    if (a.x != b.x)
        return (a.x < b.x);
    else
        return (a.y < b.y);
}
class point {
  public:
    int x, y;
    void read() {
        cin >> x >> y;
    }
} a[maxn];
class DD {
  public:
    double val;
    bool operator<(const DD &D) const {
        return D.val - val > eps;
    }
    bool operator>(const DD &D) const {
        return val - D.val > eps;
    }
};
class line {
  public:
    double k, b;
    bool ifk;
    bool operator==(const line &L) {
        return (abs(L.k - k) < eps && abs(L.b - b) < eps && ifk == L.ifk);
    }
} l[maxn];
int cmp(const point &a, const point &b) {
    if (a.x != b.x)
        return (a.x < b.x);
    else
        return (a.y < b.y);
}
line mkline(point a, point b) {
    line ans;
    ans.ifk = true;
    if (a.x == b.x) {
        ans.k = 0.0;
        ans.b = (double) (a.y + b.y) / 2.0;
    } else if (a.y == b.y) {
        ans.ifk = false;
        ans.b = (double) (a.x + b.x) / 2.0;
    } else {
        double k = (double) (b.y - a.y) * 1.0 / (double) (b.x - a.x);
        ans.k = -1 / k;
        ans.b = (a.y + b.y) * 1.0 / 2 + (a.x + b.x) * 1.0 / (2 * k);
    }
    return ans;
};
map<DD, int> expoint;
void work(line a, line b) {
    if (a.ifk && b.ifk) {
        if (abs(a.k - b.k) < eps) return;
        double x = (b.b - a.b) / (a.k - b.k);
        double y = a.k * x + a.b;
        DD poi;
        poi.val = x * 100000 + y;
        expoint[poi]++;
    } else if (a.ifk || b.ifk) {
        if (b.ifk) {
            work(b, a);
            return;
        }
        double x = b.b;
        double y = a.k * x + a.b;
        DD poi;
        poi.val = x * 100000 + y;
        expoint[poi]++;
    }
}
bool tag[maxn];
int giveans[maxn];
int main(void) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        a[i].read();
    }
    point ori;
    ori.x = 0, ori.y = 0;

    for (int i = 1; i <= n; i++) {
        l[i] = mkline(ori, a[i]);
    }

    for (int i = 1; i <= n; i++)
        giveans[i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (l[i] == l[j]) {
                tag[j] = true;
                giveans[i]++;
            }
        }
    }
    int answer = 1;
    for (int i = 1; i <= n; i++)
        if (!tag[i]) {
            expoint.clear();
            for (int j = i + 1; j <= n; j++)
                if (!tag[j]) {
                    work(l[i], l[j]);
                }
            for (auto &it : expoint) {
                answer = max(answer, it.second + 1);
            }
        }

    cout << answer;
    return 0;
}