Cod sursa(job #2394356)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 1 aprilie 2019 16:24:30
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

struct Slope {
  int up;
  int down;
  bool operator < (const Slope &other) const {
    if (up == other.up)
      return down < other.down;
    return up < other.up;
  }
  bool operator == (const Slope &other) const {
    if (up == other.up && down == other.down)
      return true;
    return false;
  }
};

struct Point {
  int x;
  int y;
};

const int MAXN = 1000, INF = 2e9 + 7;

Point a[1 + MAXN];
Slope tg[1 + MAXN * MAXN];
int lin, col;
Slope get_Slope (Point a, Point b) {
  int x = a.x - b.x;
  int y = a.y - b.y;
  int d = __gcd (x, y);
  if (d == 0) {
    if (x == 0)
      col++;
    else
      lin++;
    return {INF, INF};
  }
  x /= d; y /= d;
  return {x, y};
}

using ll = long long;

int main() {
  ll sol;
  int n, i, nr, j, l;
  freopen ("trapez.in", "r", stdin);
  freopen ("trapez.out", "w", stdout);
  scanf ("%d", &n);
  for (i = 1; i <= n; i++)
    scanf ("%d%d", &a[i].x, &a[i].y);
  nr = 0;
  for (i = 1; i <= n; i++)
    for (j = i + 1; j <= n; j++) {
      tg[++nr] = get_Slope (a[i], a[j]);
      if (tg[nr].up == INF)
        nr--;
    }
  sort (tg + 1, tg + nr + 1);
  sol = (lin * (lin - 1)) / 2 + (col * (col - 1)) / 2;
  l = 1;
  for (i = 2; i <= nr; i++)
    if (tg[i] == tg[i - 1])
      l++;
    else {
      sol += ((1LL * l * (l - 1)) / 2);
      l = 1;
    }
  sol += ((1LL * l * (l - 1)) / 2);
  printf ("%lld\n", sol);
  return 0;
}