Cod sursa(job #1649962)

Utilizator herbertoHerbert Mohanu herberto Data 11 martie 2016 15:58:11
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define MAXN 1001
#define MAXO 2000001
int lin[MAXN], col[MAXN], v[MAXN], pl[MAXN*MAXN], pc[MAXN*MAXN];
void myqsort1( int begin, int end, int *v) {
  int aux, b = begin, e = end,
    pivot = v[(begin + end) / 2];
  while ( b <= e ) {
    while ( v[b] < pivot ) b++;
    while ( v[e] > pivot ) e--;
    if ( b <= e ) {
      aux = lin[b]; lin[b] = lin[e]; lin[e] = aux;
      aux = col[b]; col[b] = col[e]; col[e] = aux;
      b++; e--;
    }
  }
  if ( begin < e ) myqsort1( begin, e ,v);
  if ( b < end ) myqsort1( b, end, v);
}

void myqsort2( int begin, int end, int *v) {
  int aux, b = begin, e = end,
    pivot = v[(begin + end) / 2];
  while ( b <= e ) {
    while ( v[b] < pivot ) b++;
    while ( v[e] > pivot ) e--;
    if ( b <= e ) {
      aux = pl[b]; pl[b] = pl[e]; pl[e] = aux;
      aux = pc[b]; pc[b] = pc[e]; pc[e] = aux;
      b++; e--;
    }
  }
  if ( begin < e ) myqsort2( begin, e ,v);
  if ( b < end ) myqsort2( b, end, v);
}

int main(){
  FILE*fin=fopen("trapez.in", "r");
  FILE*fout=fopen("trapez.out", "w");
  int n, i, a, b, r, m, k, j, trapez, nr;
  fscanf(fin, "%d", &n);
  for(i=1; i<=n; i++)
    fscanf(fin, "%d%d", &lin[i], &col[i]);
  myqsort1(1, n, lin);
  i=1;
  while(i<=n){
    k=i;
    while(lin[k]==lin[k+1] && k<=n)
      k++;
    if(k!=i)
      myqsort1(i, k, col);

    i=k+1;
  }
  k=0;
  for(i=1; i<n; i++)
    for(j=i+1; j<=n; j++){
      k++;
      a=abs(lin[j]-lin[i]);
      b=abs(col[j]-col[i]);
      if(b!=0 && a!=0){
        while(b>0){
          r=a%b;
          a=b;
          b=r;
        }
        pl[k]=(lin[j]-lin[i])/a;
        pc[k]=(col[j]-col[i])/a;
      }
      else{
        if(a==0){
          pl[k]=0;
          pc[k]=MAXO;
        }
        if(b==0){
          pl[k]=MAXO;
          pc[k]=0;
        }
      }
    }

  m=k;
  myqsort2(1, m, pl);
  i=1;
  while(i<=m){
    k=i;
    while(k<=m && pl[k]==pl[k+1])
      k++;
    if(k!=i)
      myqsort2(i, k, pc);

    i=k+1;
  }
  i=1;
  trapez=0;
  while(i<=m){
    k=i;
    while(k<m && pl[k]==pl[k+1] && pc[k]==pc[k+1])
      k++;

    nr=k-i+1;
    trapez=trapez+nr*(nr-1)/2;
    i=k+1;
  }
//  printf("%d", trapez);
//  for(i=1; i<=m; i++)
//    printf("%d %d\n", pl[i], pc[i]);
  fprintf(fout, "%d", trapez);
  return 0;
}