首页 > Boundary
开通博客写题解
头像 精神病科黄主任
发表于 2020-07-14 00:18:29
题意：给了n个点，让你自己随便定义圆心(圆心不要求是n个点的其中一个)和半径，要求这n个点有尽可能多的点在圆上，并且该圆经过坐标原点(0,0)。求满足的圆上的点最多有多少个。 思路：n是2e3，复杂度应该要小于n^3。我们知道最少三点可以确定一个圆。因为圆要求经过原点(0,0)，所以考虑n^2枚举两 展开全文
去ta的博客 赞 (26) 回复(0) 收起
头像 Lost_Deviation
发表于 2020-07-13 17:58:35
题意 在二维平面上有N（2e3）个点，需要找到一个经过原点的圆，使得这个圆经过的点最多，保证给定的点不包含原点和重复点 思路 不用板子的良心计算几何。首先有一个结论，任意两条线段的中垂线交点作为圆心，这个圆必过这两条线段的四个点，那思路就很简单了，因为必过原点，所以我们把原点和其他点连起来都求一遍中 展开全文
去ta的博客 赞 (8) 回复(1) 收起
头像 Cur1ed
发表于 2020-07-15 16:12:22
题意：给你n个点的坐标，问最多有多少个点可以在同一个圆上，（0,0）必须在这个圆上。 题解：三个点确定一个圆，所以暴力枚举两个点和（0,0）组成的圆，如果三个点不共线的话，用圆心公式求出圆心，然后用map记录以当前点为圆心的点圆的个数，边记录边判断有多少个圆圆心是同一个点，取最大值就好了。 #in 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 阿里嘎多懒羊羊桑_
发表于 2020-08-16 17:33:37
牛客多校2—— Boundary （计算几何） 题意：给出 n 个点，需要我们选择一个经过原点的圆，使得这个圆经过尽可能多的点，输出最多可以经过多少个点 思路： 三点不共线的点确定一个圆 O点已经确定，O（n）枚举另一个点P，O（n）枚举第三个点 ，这样三点就可以确定一个圆心，每次都取圆心出现最多的 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 回归梦想
发表于 2020-07-24 13:46:57
Boundary（2020多校第二场B）@[toc] 题意： 坐标平面有n个点（不与原点（0,0）重复）,现考虑一个圆，（0,0）点在圆的边界，问这个圆的边界上最多能有多少其他的点（不含原点）？我们看一下样例： 4 1 1 0 2 2 0 2 2 如图所示，我们选（0,2）为P,线段op对应的角中， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 11D_Beyonder
发表于 2020-08-11 23:19:03
题目描述   Given points in plane. Considering all circles that the origin point is on their boundries, find the one with the maximum given points on it 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 zjnu_tjq
发表于 2020-07-22 18:11:48
链接：https://ac.nowcoder.com/acm/contest/5667/B来源：牛客网 题目描述: Given n points in 2D plane. Considering all circles that the origin point (0,0) is on their 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 hairtail
发表于 2020-07-21 18:23:44
题目大意： 二维平面坐标系，给出很多无序的点，然后求出一个必过（0，0）点且边界上点最多的一个圆。 思路： 因为平面中三点确定一个圆，所以可以枚举两个点，用这两个点和原点确定圆心，这两点和原点不能关于原点对称-->否则圆心就是原点了，不在圆边界上，mp[圆心]++，然后最大值即为答案（要+1因 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”