Cod sursa(job #596953)

Utilizator stefanzzzStefan Popa stefanzzz Data 20 iunie 2011 11:55:32
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream.h>
#include <math.h>
#define DEF 232.232
#define EPS 0.001

int n,i,j;
long c[2][1001],cnt=1,nr;
double tg[499501];

void QSort(long p, long q);
long divide(long p, long q);

main(){
	freopen("trapez.in", "r", stdin);
	freopen("trapez.out", "w", stdout);
	scanf("%d", &n);
	for(i=1;i<=n;i++)
		scanf("%ld%ld", &c[0][i], &c[1][i]);
	for(i=1;i<=n-1;i++){
		for(j=i+1;j<=n;j++)
			tg[cnt++]=(c[1][j]-c[1][i]==0)?DEF:(c[0][i]-c[0][j])*1.0/(c[1][j]-c[1][i]);}
	QSort(1,cnt-1);
	for(i=2;i<cnt;i++){
		if(tg[i]-tg[i-1]<EPS)
			nr++;}
	printf("%ld", nr);
}	
		
void QSort(long p, long q){
	long m;
	m=divide(p,q);
	if(m>p+1)
		QSort(p,m-1);
	if(m<q-1)
		QSort(m+1,q);}	

long divide(long p, long q){
	long st=p, dr=q;
	double x=tg[p];
	while(st<dr){
		while(st<dr&&tg[dr]>=x)dr--;
		tg[st]=tg[dr];
		while(st<dr&&tg[st]<=x)st++;
		tg[dr]=tg[st];}
	tg[st]=x;
	return st;}