Cod sursa(job #1902636)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 4 martie 2017 18:25:26
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 1000;
const double eps = 1.e-14;

struct Point {
  int x;
  int y;
};

struct Dreapta {
  int a;
  int b;
  int c;
};

Dreapta obtineDreapta (Point p1, Point p2) {
  Dreapta d;
  d.a = p2.y - p1.y;
  d.b = p1.x - p2.x;
  d.c = p1.y * p2.x - p1.x * p2.y;
  return d;
}

double panta (Dreapta d) {
  return (double) -d.a / d.b;
}

bool cmp (double a, double b) {
  return a - b < -eps;
}

Point v[5 + MAX_N];
vector <double> pante;

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

  int N;
  scanf ("%d", &N);
  for (int i = 1; i <= N; ++i) {
    scanf ("%d%d", &v[i].x, &v[i].y);
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = i + 1; j <= N; ++j) {
      Dreapta d;
      d = obtineDreapta (v[i], v[j]);
      pante.push_back (panta (d));
    }
  }
  sort (pante.begin(), pante.end(), cmp);
  int nr = 0;
  int k = 1;
  for (int i = 1; i < pante.size(); ++i) {
    if (pante[i] - pante[i - 1] >= -eps && pante[i] - pante[i - 1] <= eps)
      ++k;
    else {
      nr += k * (k - 1) / 2;
      k = 1;
    }
  }
  nr += k * (k - 1) / 2;
  printf ("%d\n", nr);
  return 0;
}