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) {}
上一篇: 判断四个点是否构成矩形
下一篇: 判断四个点是否能形成正方形
推荐阅读
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客暑期多校训练营(第二场)C Cover the Tree
-
2020牛客暑期多校训练营(第二场)Cover the Tree 题解(dfs序)
-
一般图最大匹配 带花树 2020牛客暑期多校训练营(第二场)I 1 or 2
-
2020牛客暑期多校 第二场 B Boundary(计算几何)
-
2020牛客暑期多校第二场题解
-
2020牛客暑期多校训练营(第二场)B.Boundary(计算几何)
-
2020牛客暑期多校第二场 C - Cover the Tree(思维/贪心)
-
2020 牛客多校暑期第二场
-
2020牛客暑期多校训练营(第二场)——B