Cod sursa(job #130106)

Utilizator mgntMarius B mgnt Data 31 ianuarie 2008 11:46:09
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
using namespace std;

template < typename T >
void heap_shift (T * a, int start, int count) {
	int root, child;
	T aux;
	root = start;
	while ((child = 2 * root + 1) < count) {
		if (child < count - 1 && a [child] < a [child + 1]) ++ child;
		if (a [root] < a [child]) {
			aux = a [root]; a [root] = a [child]; a [child] = aux;
			root = child;
		} else return;
	}
}

template < typename T >
void heap_sort (T * a, int count) {
	int start, end;
	T aux;
	start = count / 2 - 1; end = count - 1;
	while (start >= 0) {
		heap_shift (a, start, count);
		-- start;
	}
	while (end > 0) {
		aux = a [0]; a [0] = a [end]; a [end] = aux;
		heap_shift (a, 0, end);
		-- end;
	}
}

typedef long long int bigint;

class dreapta {
public:
  inline void initializeaza(int x1, int y1, int x2, int y2) {
    if(x2 >= x1) {
      dx_ = x2-x1; dy_=y2-y1;
    } else {
      dx_ = x1-x2; dy_=y1-y2;
    }
  }
  inline bool operator < (dreapta const & d) const {
    if(0 == dx_) {
      if(0 != d.dx_) return true;
      return false;
    } else {
      if(0 == d.dx_) return true;
      bigint s1, s2;
      s1=dy_; s1 *= d.dx_;
      s2=d.dy_; s2 *= dx_;
      if(s1<s2) return true;
      return false;
    }
  }
  inline bool operator == (dreapta const & d) const {
    if(0 == dx_) {
      if(0 != d.dx_) return false;
      return true;
    } else {
      if(0 == d.dx_) return false;
      bigint s1, s2;
      s1=dy_; s1 *= d.dx_;
      s2=d.dy_; s2 *= dx_;
      if(s1==s2) return true;
      return false;
    }
  }
private:
  int dx_, dy_;
};

struct punct {
  int x, y;
};

int const MAXN = 1000;
dreapta v[(MAXN * (MAXN-1))/2]; // comb
punct   p[MAXN];


int main() {
  int n, m, i, j, num, sum;
  FILE * io;
  io = fopen ("trapez.in", "r");
  setvbuf(io, NULL, _IOFBF, 1024 * 1024);
  fscanf(io, "%d", &n);
  for(i=0;i<n;i++) {
    fscanf(io, "%d %d", &p[i].x, &p[i].y);
  }
  for(i=0, m=0;i<n;i++) {
    for(j=i+1;j<n;j++) {
      v[m].initializeaza(p[i].x, p[i].y, p[j].x, p[j].y);
      ++ m;
    }
  }
  
  fclose(io);
  heap_sort < dreapta > (v, m);
  for(i=1, num=0, sum=0;i<m;i++) {
    if(v[i]==v[i-1]) {
      ++ num;
    } else {
      sum += (num * (num-1))/2; // comb
      num  = 1;
    }
  }
  sum += (num * (num-1))/2;
  io = fopen("trapez.out", "w");
  fprintf(io, "%d\n", sum);
  fclose(io);
  return 0;
}