题解

拾取糖果

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

B

本题不需要求斜率

  1. 该题直线穿过x1,y2;x2,y2,假设y2,x2大,那y2和y1一定存在一个整数倍的关系,__gcd(x,y)求出最大的公约数
  2. 可以map<{x,y},m>将每个斜率最小的值存下来
  3. 负数和正数的斜率是一样的,可以把负数转化成正数
      #include<bits/stdc++.h>
      
      using namespace std;
      typedef long long ll;
      ll n,z;
      typedef pair<int,int> pii;
      template<class T> bool chmax(T &a, T b) {
          if (a >= b) return false;
          a = b; return true;
      }
      int main(){
          ios::sync_with_stdio(0);
          cin.tie(0);
          cout.tie(0);
          cin>>n;
          map<pii ,int>m;
          while(n--){
              ll x,y;
              cin>>x>>y;
              if(x==0&&y==0) z++;
              else{
                  int d=__gcd(x,y);
                  x/=d,y/=d;
                  if(x<0) x=-x, y=-y;//关于原点对称的在负数的全部转成正数
                  m[{x,y}]++;
              }
          }
          int mx=0;
          for(auto &e:m) chmax(mx,e.second);
          cout<<mx+z<<endl;
          return 0;
      }    
      
                           ```
      
全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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