Cod sursa(job #2266790)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 22 octombrie 2018 21:27:38
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 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 MAXBUF = 30000000;
char parseBuf[MAXBUF];
char *head;
bool isDigit[255];

void parseInit() {
  int a = fread(parseBuf, 1, MAXBUF, stdin);
  parseBuf[a] = 0;
  head = parseBuf;
  memset(isDigit, 0, sizeof isDigit);
  for (int i = '0'; i <= '9'; ++i)
    isDigit[i] = true;
}

int nextInt() {
  int ans = 0;
  for (; !isDigit[*head]; ++head);
  for (; isDigit[*head]; ++head)
    ans = ans * 10 + (*head) - '0';
  return ans;
}

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

LL hsh(int x, int y) {
  if (x == 0)
    y = 1;
  else if (y == 0)
    x = 1;
  else {
    int g = __gcd(x, y);
    x /= g;
    y /= g;
  }
  return 1LL * x * INT_MAX + y;
}

struct node {
  LL key;
  int freq;
  node *nxt;
} phys[MAXN * MAXN];
int nxtNode = 0;

const int BUCKETS = MAXN * MAXN * 4;
node *b[BUCKETS];

void update(LL elem) {
  int key = (int)(elem % (BUCKETS / 2));
  if (key < 0) key += (BUCKETS / 2);
  for(node *t = b[key]; t; t = t->nxt)
    if (t->key == elem) {
      t->freq += 1;
      return;
    }
  phys[nxtNode].key = elem;
  phys[nxtNode].freq = 1;
  phys[nxtNode].nxt = b[key];
  b[key] = &phys[nxtNode];
  ++nxtNode;
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  parseInit();
  N = nextInt();
  for (int i = 0; i < N; ++i) {
    v[i].first = nextInt(), v[i].second = nextInt();
    for (int j = i - 1; j >= 0; --j)
      update(hsh(v[j].second - v[i].second,
        v[j].first - v[i].first));
  }
  LL ans = 0;
  for (int i = 0; i < BUCKETS; ++i)
    for (node *t = b[i]; t; t = t->nxt)
      ans += 1LL * t->freq * (t->freq - 1) / 2;
  printf("%lld\n", ans);
  return 0;
}