Cod sursa(job #2844862)

Utilizator Teodor94Teodor Plop Teodor94 Data 5 februarie 2022 19:13:43
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

#define int64 long long

struct Point { int x, y; };

struct Fraction { int a, b; };

bool isEqual(const Fraction& f1, const Fraction& f2) {
  return (int64)f1.a * f2.b == (int64)f1.b * f2.a;
}

bool isLesser(const Fraction& f1, const Fraction& f2) {
  if ((int64)f1.b * f2.b > 0)
    return (int64)f1.a * f2.b < (int64)f1.b * f2.a;
  return (int64)f1.a * f2.b > (int64)f1.b * f2.a;
}

#define MAX_N 1000
const int MAX_P = (MAX_N - 1) * MAX_N / 2;

Point v[MAX_N];
Fraction slopes[MAX_P];

Fraction getSlope(const Point& a, const Point& b) {
  return {b.y - a.y, b.x - a.x};
}

int main() {
  FILE *fin, *fout;
  fin = fopen("trapez.in", "r");
  fout = fopen("trapez.out", "w");

  int n, i, j, noSlopes, noInfSlopes;
  int64 counter;
  fscanf(fin, "%d", &n);
  for (i = 0; i < n; ++i)
    fscanf(fin, "%d%d", &v[i].x, &v[i].y);

  noSlopes = noInfSlopes = 0;
  for (i = 1; i < n; ++i)
    for (j = 0; j < i; ++j)
      if (v[i].x == v[j].x)
        ++noInfSlopes;
      else
        slopes[noSlopes++] = getSlope(v[j], v[i]);

  sort(slopes, slopes + noSlopes, isLesser);

  counter = (int64)(noInfSlopes - 1) * noInfSlopes / 2;
  i = 0;
  while (i < noSlopes) {
    j = i;
    while (j < noSlopes && isEqual(slopes[i], slopes[j]))
      ++j;

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

  fprintf(fout, "%lld\n", counter);

  fclose(fin);
  fclose(fout);
  return 0;
}