yicongli

Gym 313459D

Jan 24th, 2021
514
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8. #define db double
  9.  
  10. template<typename T>
  11. inline void read(T&x){
  12.     x=0;T k=1;char gc;
  13.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  14.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  15. }
  16.  
  17. const int N=105;
  18. const db eps=1e-6;
  19.  
  20. inline db sqr(db x){
  21.     return x*x;
  22. }
  23.  
  24. inline int dcmp(const db &x){
  25.     if(fabs(x)<eps)return 0;
  26.     return x>0?1:-1;
  27. }
  28.  
  29. struct Point{
  30.     db x,y;
  31.    
  32.     inline Point(){}
  33.     inline Point(db _x,db _y):x(_x),y(_y){}
  34.    
  35. };
  36.  
  37. #define Vec Point
  38.  
  39. inline Vec operator +(const Vec &a,const Vec &b){
  40.     return Vec(a.x+b.x,a.y+b.y);
  41. }
  42.  
  43. inline Vec operator -(const Vec &a,const Vec &b){
  44.     return Vec(a.x-b.x,a.y-b.y);
  45. }
  46.  
  47. inline void operator +=(Vec &a,const Vec &b){
  48.     a.x+=b.x,a.y+=b.y;
  49. }
  50.  
  51. inline void operator -=(Vec &a,const Vec &b){
  52.     a.x-=b.x,a.y-=b.y;
  53. }
  54.  
  55. inline Vec operator *(const Vec &a,const db &b){
  56.     return Vec(a.x*b,a.y*b);
  57. }
  58.  
  59. inline Vec operator /(const Vec &a,const db &b){
  60.     return Vec(a.x/b,a.y/b);
  61. }
  62.  
  63. inline db Norm(const Vec &a){
  64.     return sqrt(sqr(a.x)+sqr(a.y));
  65. }
  66.  
  67. inline Point Middle(const Point &A,const Point &B){
  68.     return (A+B)/2;
  69. }
  70.  
  71. inline Vec I(const Vec &a){
  72.     return a/Norm(a);
  73. }
  74.  
  75. inline db Dis(const Point &A,const Point &B){
  76.     return Norm(A-B);
  77. }
  78.  
  79. inline Vec Rotate(const Vec &A){
  80.     return Vec(-A.y,A.x);
  81. }
  82.  
  83.  
  84. Point P[N];
  85.  
  86. int main(){
  87.     // freopen(".in","r",stdin);
  88.     // freopen(".out","w",stdout);
  89.     int R;r(R);
  90.     int n;r(n);
  91.     for(int i=0;i<n;++i){
  92.         int x,y;r(x),r(y);
  93.         P[i]=Point(x,y);
  94.     }
  95.     int ans=1;
  96.     for(int i=0;i<n;++i){
  97.         for(int j=i+1;j<n;++j){
  98.             db tmp=Dis(P[i],P[j]);
  99.             if(dcmp(tmp-2*R)>0)continue;
  100.             Point M=Middle(P[i],P[j]);
  101.             db len=sqrt(R*R-tmp*tmp/4);
  102.             Point C=M+Rotate(I(P[i]-P[j]))*len;
  103.             int cnt=0;
  104.             for(int k=0;k<n;++k){
  105.                 if(dcmp(Dis(C,P[k])-R)<=0)cnt++;
  106.                 ans=max(ans,cnt);
  107.             }
  108.             C=M-Rotate(I(P[i]-P[j]))*len;
  109.             cnt=0;
  110.             for(int k=0;k<n;++k){
  111.                 if(dcmp(Dis(C,P[k])-R)<=0)cnt++;
  112.                 ans=max(ans,cnt);
  113.             }
  114.         }
  115.     }
  116.     printf("%d\n",ans);
  117.     return 0;
  118. }
RAW Paste Data