Cod sursa(job #1744592)

Utilizator TincaMateiTinca Matei TincaMatei Data 19 august 2016 23:11:08
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <cstdio>
#include <cstdlib>

const int MAX_N = 1000;
const int MAX_DREPTE = MAX_N * (MAX_N + 1) / 2;

int xp[MAX_N], yp[MAX_N];
int pantaX[MAX_DREPTE], pantaY[MAX_DREPTE];

int cmmdc(int a, int b) {
  int r;
  r = a % b;
  while(r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

int compPanta(int x1, int y1, char semn, int x2, int y2) {
  if(semn == '<')
    return (x1 < x2) || (x1 == x2 && y1 < y2);
  else //if(semn == '>')
    return (x1 > x2) || (x1 == x2 && y1 > y2);
}

void qSort(int begin, int end) {
  int b, e, aux, pivotX, pivotY;
  b = begin;
  e = end;
  pivotX = pantaX[(b + e) / 2];
  pivotY = pantaY[(b + e) / 2];
  while(b <= e) {
    while(compPanta(pantaX[b], pantaY[b], '<', pivotX, pivotY)) b++;
    while(compPanta(pantaX[e], pantaY[e], '>', pivotX, pivotY)) e--;
    if(b <= e) {
      aux = pantaX[b];
      pantaX[b] = pantaX[e];
      pantaX[e] = aux;
      aux = pantaY[b];
      pantaY[b] = pantaY[e];
      pantaY[e] = aux;
      b++;
      e--;
    }
  }
  if(begin < e)
    qSort(begin, e);
  if(b < end)
    qSort(b, end);
}

int main() {
  int n, i, j, k, r, egale, sol;
  FILE *fin = fopen("trapez.in", "r");
  fscanf(fin, "%d", &n);
  k = 0;
  for(i = 0; i < n; i++) {
    fscanf(fin, "%d%d", &xp[i], &yp[i]);
    for(j = 0; j < i; j++) {
      pantaX[k] = xp[i] - xp[j];
      pantaY[k] = yp[i] - yp[j];
      if(pantaX[k] == 0)
        pantaY[k] = 1;
      else if(pantaY[k] == 0)
        pantaX[k] = 1;
      else {
        r = cmmdc(pantaX[k], pantaY[k]);
        pantaX[k] /= r;
        pantaY[k] /= r;
      }
      k++;
    }
  }
  fclose(fin);

  qSort(0, k - 1);

  egale = 1;
  sol = 0;
  for(i = 1; i < k; i++) {
    if(pantaX[i] == pantaX[i - 1] && pantaY[i] == pantaY[i - 1]) {
      egale++;
      sol = sol + egale - 1;
    } else
      egale = 1;
  }

  FILE *fout = fopen("trapez.out", "w");
  fprintf(fout, "%d", sol);
  fclose(fout);
  return 0;
}