区块链技术博客
www.b2bchain.cn

2020牛客暑假多校第二场 B Boundary (数学/map+三点共圆圆心公式)的讲解

这篇文章主要介绍了2020牛客暑假多校第二场 B Boundary (数学/map+三点共圆圆心公式)的讲解,通过具体代码讲解7424并且分析了2020牛客暑假多校第二场 B Boundary (数学/map+三点共圆圆心公式)的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了2020牛客暑假多校第二场 B Boundary (数学/map+三点共圆圆心公式)的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7424.html。具体如下:

Boundary

题目链接:题目链接

题目大意:

二维平面坐标系,给出很多无序的点,然后求出一个必过(0,0)点且边界上点最多的一个圆。

思路:

因为平面中三点确定一个圆,所以可以枚举两个点,用这两个点和原点确定圆心,这两点和原点不能关于原点对称–>否则圆心就是原点了,不在圆边界上,mp[圆心]++,然后最大值即为答案(要+1因为要加上原点)。

Code:

#include<iostream> #include<stdio.h> #include<string.h> #include<vector> #include<map> #include<queue> #include<algorithm> #define ll long long using namespace std; const int maxn = 2e6+7; const int mod=1e9+7; int n,m,k,ans; struct node{ 	double x,y; }p[maxn];  map<pair<double,double>,int> mp;  void solve(node a,node b,node c){ //三点求圆心公式  	 	double x=( (a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)*(a.y-c.y)-(a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y)*(a.y-b.y) ) / (2.0*(a.y-c.y)*(a.x-b.x)-2*(a.y-b.y)*(a.x-c.x));     double y=( (a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)*(a.x-c.x)-(a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y)*(a.x-b.x) ) / (2.0*(a.y-b.y)*(a.x-c.x)-2*(a.y-c.y)*(a.x-b.x));     mp[{x,y}]++;     ans=max(ans,mp[{x,y}]); }  int main() { 	ios::sync_with_stdio(0); 	cin.tie(0);cout.tie(0); 	int n; 	cin>>n; 	for(int i=1;i<=n;i++){ 		cin>>p[i].x>>p[i].y; 	} 	p[0].x=0.0; p[0].y=0.0; ans=0;     for(int i=1;i<=n;i++){     	mp.clear();     	for(int j=i+1;j<=n;j++){     		if(p[i].x*p[j].y==p[i].y*p[j].x) continue; //不能关于原点对称      		solve(p[0],p[i],p[j]); 		} 	} 	cout<<ans+1<<endl;     return 0; }  

本文地址https://www.b2bchain.cn/7424.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 2020牛客暑假多校第二场 B Boundary (数学/map+三点共圆圆心公式)的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们