Cod sursa(job #566270)

Utilizator maritimCristian Lambru maritim Data 28 martie 2011 20:30:03
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef struct _nod
{
	long int a;
	long int b;
	struct _nod *adr;
} nod;

typedef struct
{
	long int x;
	long int y;
} xy;

xy A[1001];
xy B[100001];
int N;
nod *cap = NULL;
int nr = 0;
int acc = 0;

void citire(void)
{
	FILE *f = fopen("trapez.in","r");
	
	fscanf(f,"%d ",&N);
	for(int i=1;i<=N;i++)
		fscanf(f,"%d %d",&A[i].x,&A[i].y);
	
	fclose(f);
}

void add(int a,int b)
{
	B[++acc].x = A[a].y-A[b].y;
	B[acc].y = A[a].x-A[b].x;
}

void creare(void)
{
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;j++)
			add(i,j);
}

void calc(void)
{
	int j;
	for(int i=1;i<=acc;i++)
	{
		j = i+1;
		while(j<=acc && B[i].x*B[j].y == B[i].y*B[j].x)
		{
			nr++;
			j ++;
		}
	}
}

long int poz(int li,int ls)
{
	xy a = B[(li+ls)/2];
	B[(li+ls)/2] = B[1];
	B[1] = a;
	int c;
	int i1 = 0;
	int j1 = -1;
	int b;
	int d;
	while(li<ls)
	{
		if(B[li].y<0)
			b = -1;
		else
			b = 1;
		if(B[ls].y<0)
			d = -1;
		else
			d = 1;
		if(b*B[li].x*d*B[ls].y>b*B[li].y*d*B[ls].x)
		{
			a = B[li];
			B[li] = B[ls];
			B[ls] = a;
			c = -i1;
			i1 = -j1;
			j1 = c;
		}
		li += i1;
		ls += j1;
	}
	return li;
}

void qsort(int li,int ls)
{
	if(li<ls)
	{
	long int k = poz(li,ls);
	qsort(li,k-1);
	qsort(k+1,ls);
	}
}

int main()
{
	FILE *f = fopen("trapez.out","w");
	
	citire();
	creare();
	qsort(1,acc);
	calc();
	fprintf(f,"%d",nr);
	
	fclose(f);
	return 0;
}