Advertisement
Guest User

Untitled

a guest
May 20th, 2018
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define sc(a) scanf("%d", &a)
  4. #define sc2(a, b) scanf("%d %d", &a, &b)
  5. #define sc3(a, b, c) scanf("%d %d %d", &a, &b, &c)
  6. #define pri(x) printf("%d\n", x)
  7. #define prie(x) printf("%d ", x)
  8. #define mp make_pair
  9. #define pb push_back
  10. #define BUFF ios::sync_with_stdio(false);
  11. #define db(x) cerr << #x << " == " << x << endl;
  12. typedef long long ll;
  13. typedef long double ld;
  14. typedef pair<ll, ll> ii;
  15. typedef vector<int> vi;
  16. typedef vector<ii> vii;
  17. const int INF = 0x3f3f3f3f;
  18. const ll LINF = 0x3f3f3f3f3f3f3f3fll;
  19. const ld pi = acos(-1);
  20. const int MOD = 1e9 + 7;
  21. const int N = 1e6;
  22. vii v;
  23. map< pair<ii,ii>, int> retas;
  24. map<int, int> mapx, mapy;
  25. ll gcd(ll a, ll b){
  26.     if(b==0) return a;
  27.     return gcd(b, a%b);
  28. }
  29. int main() {
  30.     int t=1;
  31.     sc(t);
  32.     while(t--){
  33.         int n;
  34.         sc(n);
  35.         retas.clear(), mapx.clear(), mapy.clear();
  36.         int resp = 1;
  37.         for(int i=1;i<=n;i++){
  38.             int x, y;
  39.             sc2(x, y);
  40.             v.pb({mp(x, y)});
  41.             mapx[x]++, mapy[y]++;
  42.             resp = max(resp, mapx[x]);
  43.             resp = max(resp, mapy[y]);
  44.         }
  45.         for(int i=0;i<n;i++){
  46.             retas.clear();
  47.             for(int j=i+1;j<n;j++){
  48.                 ll dx = v[i].first - v[j].first;
  49.                 ll dy = v[i].second - v[j].second;
  50.                 ll k = gcd(abs(dx), abs(dy));
  51.                 if(dx == 0) continue;
  52.                 dx /= k;
  53.                 dy /=k;
  54.                 ii a = mp(dy, dx);
  55.                 ii b;
  56.                 b.first = v[j].second*dx - dy*v[j].first;
  57.                 b.second = dx;
  58.                 k = gcd(abs(b.first), abs(b.second) );
  59.                 b.first/= k;
  60.                 b.second/=k;
  61.                 retas[mp(a, b)]++;
  62.                 resp = max(retas[mp(a, b)] + 1, resp);
  63.             }
  64.         }
  65.         pri(resp);
  66.     }
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement