Cod sursa(job #2876525)

Utilizator YusyBossFares Yusuf YusyBoss Data 23 martie 2022 12:06:14
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda masonii Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define NMAX 1000

using namespace std;

ifstream cin ("trapez.in");
ofstream cout ("trapez.out");

map <pair<int, int>, int> mp;
pair <int, int> v[NMAX + 1], vfractii[NMAX * NMAX + 1];

bool cmp(pair <int, int> A, pair <int, int> B) {
  return (long long)A.first * B.second < (long long)A.second * B.first;
}

bool is_equal(pair <int, int> A, pair <int, int> B) {
  return A.first == B.first && A.second == B.second;
}

int main() {
  int n, i, j, sol, a, b, cnt, gcd, nfractii;
  cin >> n;

  for (i = 0; i < n; i++)
    cin >> v[i].first >> v[i].second;

  cnt = nfractii = 0;
  for (i = 0; i < n; i++) {
    for (j = i + 1; j < n; j++) {
      gcd = __gcd(v[i].second - v[j].second, v[i].first - v[j].first);
      vfractii[nfractii++] = {(v[i].second - v[j].second) / gcd, (v[i].first - v[j].first) / gcd};
    }
  }

  sort(vfractii, vfractii + nfractii, cmp);

  cnt = 1;
  for (i = 1; i < nfractii; i++) {
    if (is_equal(vfractii[i], vfractii[i - 1]))
      cnt++;
    else {
      sol += cnt * (cnt - 1) / 2;
      cnt = 1;
    }
  }

  sol += cnt * (cnt - 1) / 2;

  cout << sol;
  return 0;
}