Facebook
From shadow9236, 1 Year ago, written in C++.
Embed
Download Paste or View Raw
Hits: 159
  1. // हर हर महादेव
  2. using namespace std;
  3. #include <bits/stdc++.h>
  4. #define int long long int
  5.  
  6. int solve(vector<pair<int,int>> &a){
  7.         if(a.empty()){
  8.                 return 0;
  9.         }
  10.        
  11.         int n = a.size();
  12.         for(auto &[x,y] : a){
  13.                 x = abs(x);
  14.                 y = abs(y);
  15.         }
  16.        
  17.         sort(a.begin(),a.end(),[&](const auto &v1,const auto &v2){
  18.                 auto [x1,y1] = v1;
  19.                 auto [x2,y2] = v2;
  20.                 if(x1*y2 != x2*y1){
  21.                         return x1*y2 < x2*y1;
  22.                 }
  23.                 return x1*x1 + y1*y1 < x2*x2 + y2*y2;
  24.         });
  25.        
  26.         int ans = 1;
  27.         for(int i = 1; i < n; i++){
  28.                 auto [x1,y1] = a[i];
  29.                 auto [x2,y2] = a[i-1];
  30.                 if(x1*y2 != x2*y1){
  31.                         ans++;
  32.                 }
  33.         }
  34.         return ans;
  35. }
  36.  
  37. void testcase(){
  38.         int n;
  39.         cin >> n;
  40.         vector<pair<int,int>> a(n);
  41.        
  42.         for(int i = 0; i < n; i++){
  43.                 cin >> a[i].first >> a[i].second;
  44.         }
  45.        
  46.         bool sp = false;
  47.        
  48.         vector<pair<int,int>> p;
  49.         vector<pair<int,int>> q;
  50.         vector<pair<int,int>> r;
  51.         vector<pair<int,int>> s;
  52.        
  53.        
  54.         for(auto &[x,y] : a){
  55.                 if(x == 0 && y == 0){
  56.                         cout << "1\n";
  57.                         return;
  58.                 }
  59.                 if(x >= 0){
  60.                         if(y >= 0){
  61.                                 p.push_back({x,y});
  62.                         }
  63.                         else{
  64.                                 q.push_back({x,y});
  65.                         }
  66.                 }
  67.                 else{
  68.                         if(y >= 0){
  69.                                 r.push_back({x,y});
  70.                         }
  71.                         else{
  72.                                 s.push_back({x,y});
  73.                         }
  74.                 }
  75.         }
  76.         cout << solve(p) + solve(q) + solve(r) + solve(s) << '\n';
  77. }
  78.  
  79. int32_t main(){
  80.         ios::sync_with_stdio(false);
  81.         cin.tie(0);
  82.         int tt = 1;
  83.         cin >> tt;
  84.         while(tt--){
  85.                 testcase();
  86.         }
  87.         return (0-0);
  88. }
  89.