c/c++语言开发共享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) {} 

c/c++开发分享2020牛客暑期多校训练营（第二场）B.Boundary(计算几何)地址：https://blog.csdn.net/qq_43054573/article/details/107345948