Cod sursa(job #2340409)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 10 februarie 2019 13:46:22
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define x first
#define y second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

template <class T> void uin (T &a, T b) {a = min (a, b);}
template <class T> void uax (T &a, T b) {a = max (a, b);}

ifstream f ("trapez.in");
ofstream g ("trapez.out");

const int NMAX = 1e3 + 5;

pii points[NMAX];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen (".in", "r", stdin);
#endif

  int n;
  f >> n;
  for (int i = 1; i <= n; ++i) {
    int x, y;
    f >> x >> y;
    points[i] = {x, y};
  }

  vector <pii> slopes;
  int cnt_vertical = 0, cnt_horizontal = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      int dx = points[j].x - points[i].x;
      int dy = points[j].y - points[i].y;

      if (dx == 0) {
        ++cnt_vertical;
      } else if (dy == 0) {
        ++cnt_horizontal;
      } else {
        int gcd = __gcd (dx, dy);
        dx /= gcd;
        dy /= gcd;

        slopes.pb ({dy, dx});
      }
    }
  }

  sort (all (slopes));

  int ans = cnt_horizontal * (cnt_horizontal - 1) / 2 +
            cnt_vertical * (cnt_vertical - 1) / 2;
  int sz = slopes.size(), cnt = 0;
  for (int i = 0; i < sz; ++i) {
    if (i == 0 || slopes[i] == slopes[i - 1]) {
      ++cnt;
    } else {
      ans += cnt * (cnt - 1) / 2;
      cnt = 1;
    }
  }

  g << ans << '\n';

  f.close();
  g.close();

#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}