2020牛客暑期多校训练营（第二场）B.Boundary(计算几何)

B-Boundary

题意：给定原点及n个点，找到一个圆使得尽可能多的点在圆上
题解：三点可以确定一个圆，原点固定，遍历两个点去确定圆心，并用map保存圆心，当再次得到一个相同的圆心时，map++（圆心相同，且有共点必定为同一个圆）
为避免重复计算某一点，每次遍历完第一维之后，清空map，相当于每一次固定原点和定点P，遍历第三点Q，最后结果要加上P

由于圆心推导的式子有点小问题，所以一直只能过95%（55555…），后面给出三点确定圆心的模板

Code：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int, int>
#define pdd pair<db, db>
#define mem(a, b) memset(a, b, sizeof(a));
#define lowbit(x) (x & -x)
#define lrt nl, mid, rt << 1
#define rrt mid + 1, nr, rt << 1 | 1
template <typename T>
inline void read(T& t) {
    t = 0;
    int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        t = t * 10 + ch - '0';
        ch = getchar();
    }
    t *= f;
}
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const ll Inf = 0x7f7f7f7f7f7f7f7f;
const int inf = 0x7f7f7f7f;
const db eps = 1e-5;
const db Pi = acos(-1);
const int maxn = 2e3 + 10;

struct Point {
    db x, y;
} an[maxn];

map<pdd, int> mp;

int main(void) {
    int n;
    read(n);
    for (int i = 1; i <= n; i++)
        scanf("%lf %lf", &an[i].x, &an[i].y);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        mp.clear();
        for (int j = i + 1; j <= n; j++) {
            db x1 = an[i].x, x2 = an[j].x, y1 = an[i].y, y2 = an[j].y, x3 = 0,
               y3 = 0;
            db a = x1 - x2;
            db b = y1 - y2;
            db c = x1 - x3;
            db d = y1 - y3;
            db e = ((x1 * x1 - x2 * x2) + (y1 * y1 - y2 * y2)) / 2.0;
            db f = ((x1 * x1 - x3 * x3) + (y1 * y1 - y3 * y3)) / 2.0;
            db det = b * c - a * d;
            if (fabs(det) < eps)
                continue;
            db x = -(d * e - b * f) / det;
            db y = -(a * f - c * e) / det;
            ans = max(ans, ++mp[{x, y}]);
        }
    }
    printf("%d", ans + 1);
    return 0;
}

三点确定圆心模板：

#include <bits/stdc++.h>
using namespace std;
#define db double
#define pdd pair<db, db>
const db eps = 1e-5;

pdd Circle_center(db x1, db x2, db x3, db y1, db y2, db y3) {
    db a = x1 - x2;
    db b = y1 - y2;
    db c = x1 - x3;
    db d = y1 - y3;
    db e = ((x1 * x1 - x2 * x2) + (y1 * y1 - y2 * y2)) / 2.0;
    db f = ((x1 * x1 - x3 * x3) + (y1 * y1 - y3 * y3)) / 2.0;
    db det = b * c - a * d;
    if (fabs(det) < eps)  //三点共线
        return {0, 0};
    db x = -(d * e - b * f) / det;
    db y = -(a * f - c * e) / det;
    return {x, y};
}

int main(void) {}