Mai intai trebuie sa te autentifici.

Cod sursa(job #2266668)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 22 octombrie 2018 20:24:26
Problema Trapez Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#define CHECKRET(x, y) if(!(x)) return (y);
#define SKIP(x) if((x)) continue;
typedef pair<int, int> pii;

#ifdef INFOARENA
#define ProblemName "trapez"
#else
#define ProblemName "fis"
#endif

#define InFile ProblemName ".in"
#define OuFile ProblemName ".out"

const int MAXN = 1010;
pii v[MAXN];
int N;

struct fractie {
  int sus, jos;
  fractie(int x, int y) : sus(x), jos(y) {}
  bool operator==(const fractie &other) const {
    return 1LL * sus * other.jos ==
      1LL * jos * other.sus;
  }
};

struct KeyHasher {
  std::size_t operator()(const fractie& k) const {
    if (k.sus == 0) return 0;
    if (k.jos == 0) return 13258215;
    return max(k.sus / k.jos, k.jos / k.sus);
  }
};

unordered_map<fractie, int, KeyHasher> pantaFreq;

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    scanf("%d%d", &v[i].first, &v[i].second);
    for (int j = i - 1; j >= 0; --j)
      ++pantaFreq[fractie(v[j].second - v[i].second,
        v[j].first - v[i].first)];
  }
  int ans = 0;
  for (const auto &it : pantaFreq)
    ans += it.second * (it.second - 1) / 2;
  printf("%d\n", ans);
  return 0;
}