Cod sursa(job #2396838)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 3 aprilie 2019 21:08:20
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 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;

}