Cod sursa(job #2091885)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 20 decembrie 2017 15:13:36
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1005

int n;

struct Point {
  int x, y;
}p[MAXN];

struct Rational {
  long long a, b; /// a/b

  bool isInfinity() { return b == 0; }
};

vector<Rational> slopes;

Rational slope(Point first, Point second) {
  Rational result;
  result.a = first.x - second.x;
  result.b = first.y - second.y;
  return result;
}

bool cmp(Rational first, Rational second) {
  return 1LL*first.a * second.b < 1LL*second.a * first.b;
}

int main() {
  freopen("trapez.in", "r", stdin);
  freopen("trapez.out", "w", stdout);

  scanf("%d ", &n);

  for (int i = 1; i <= n; i++) {
    scanf("%d %d ", &p[i].x, &p[i].y);
  }

  int counter = 0;

  for (int i = 1; i < n; i++) {
    for (int j = i + 1; j <= n; j++) {
      Rational s = slope(p[i], p[j]);
      if (s.isInfinity())
        ++counter;
      else {
        if (s.b < 0) {
          s.b *= -1;
          s.a *= -1;
        }
        slopes.push_back(s);
      }
    }
  }

  counter = counter * (counter - 1) / 2;

  sort(slopes.begin(), slopes.end(), cmp);

  int i = 0;

  while ( i < slopes.size() ) {
    int cnt = 0, j = i;
    while ( j < slopes.size() && slopes[i].a * slopes[j].b == slopes[j].a * slopes[i].b ) {
      cnt++;
      j++;
    }

    counter += cnt * (cnt - 1) / 2;
    i = j;
  }

  printf("%d\n", counter);

  return 0;
}