2020牛客暑期多校(第二场)B

Boundary

https://ac.nowcoder.com/acm/contest/5667/B

题目描述

  Given points in plane. Considering all circles that the origin point is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.

输入描述

  The first line contains one integer , denoting the number of given points.
  Following lines each contains two integers , denoting a given point .
  It's guaranteed that the points are pairwise different and no given point is the origin point.

输出描述

  Only one line containing one integer, denoting the answer.

示例1

输入

4  
1 1  
0 2  
2 0  
2 2

输出

3  

说明

  Considering circle , we can see that the origin point is on its boundry and that there are given points on its boundry.

分析

  不共线的三点确定一个圆,已知其中一个点为 ,可以在 的时间内枚举得到另外两个点,得到不共线的三点后,可以轻易计算出三点所确定的圆心。
  当第一层枚举得到点 ,那么再枚举一个点即可得到圆心,若第三个点 和原点确定的圆心都为 ,那么 都被同一个圆的边界覆盖。第一层枚举后,用 记录在 边界上的点(第二层枚举得到的点)的个数,取最大即可,因为圆上的点还有第一层枚举得到的点,最大值还要增加
  枚举的方式,可保证不重复不遗漏。若枚举点 ,有 都与 在同一个圆上,那么有 个点在同一个圆上;当下一次枚举到 ,第三层枚举不会涉及到 ,可以确定的是,会得到有 在同一点上。

for(i=1;i<=n;i++)
{
    for(j=i+1;j<=n;j++)
    {
        \\function
    }
}

代码

#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const double eps=1e-6;
const int N=2005;
int n;
struct CPoint 
{
    double x;
    double y;
    bool operator<(const CPoint& A)const
    {
        if(x==A.x) return A.y-y>eps;
        else return A.x-x>eps;
    }
}p[N];
map<CPoint,int>cnt;
int main()
{
    cin>>n;
    int i,j;
    for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    int ans=1;//至少能覆盖一个点
    for(i=1;i<=n;i++)
    {
        cnt.clear();
        for(j=i+1;j<=n;j++)
        {
        //===========================================
        //三点确定圆心模板
            double x1=0,y1=0;
            double x2=p[i].x,y2=p[i].y;
            double x3=p[j].x,y3=p[j].y;
            double a=x1-x2;
            double b=y1-y2;
            double c=x1-x3;
            double d=y1-y3;
            double e=((x1*x1-x2*x2)-(y2*y2-y1*y1))/2;
            double f=((x1*x1-x3*x3)+(y1*y1-y3*y3))/2;
            if(fabs(b*c-a*d)<eps) continue;
            CPoint C;//圆心
            C.x=(b*f-d*e)/(b*c-a*d);
            C.y=(c*e-a*f)/(b*c-a*d);
        //============================================
            cnt[C]++;//j1,j2,...,jk
        }
        //+1 囊括第一层枚举的点
        for(auto v:cnt) ans=max(ans,v.second+1);
    }
    cout<<ans<<endl;
    return 0;
}
牛客暑期多校训练营题解 文章被收录于专栏

收集牛客暑期多校训练营的题解

全部评论

相关推荐

06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 10:56
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务