欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-02 10:54:18
...

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) {}