Cod sursa(job #63038)

Utilizator c_sebiSebastian Crisan c_sebi Data 25 mai 2007 20:32:45
Problema Trapez Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#include <math.h>
#define INF 2000000001
#define MAXN 1000
int n, k, alfa;
struct U {int x, y;} P[MAXN], s[MAXN*(MAXN-1)/2];

void quick (U x[], int st, int dr)
{
	int i, ii, j, jj, aux2;
	U aux;
	i=st; j=dr;
	ii=0; jj=-1;
 if (st<dr)
{	while (i<j)
		{
			if ((long long)(x[i].x*x[j].y-x[j].x*x[i].y)*(x[i].y*x[j].y)>0)
				{ aux=x[i]; x[i]=x[j]; x[j]=aux;
				  aux2=-ii; ii=-jj; jj=aux2;
				}
			i=i+ii;
			j=j+jj;
		}
	quick(x, st, i-1);
	quick(x, i+1, dr);
 }
}


void read()
{
	int i;
	freopen ("trapez.in", "r", stdin);
	scanf ("%d", &n);
	for (i=0; i<n; ++i)
		scanf("%d %d", &P[i].x, &P[i].y);
	fclose(stdin);
}

void slope()
{
	int i, j;
	for (i=0; i<n; ++i)
		for (j=i+1; j<n; ++j)
			{
				if (P[i].x==P[j].x)
					alfa++;
				else s[k].x = (P[i].y-P[j].y), s[k++].y=(P[i].x-P[j].x);
			}
}

int main()
{
	int i, j, nr=0, a, b, v;
	read();
	slope();
	quick(s, 0, k-1);
	for (i=0; i<k; )
		{
			a=s[i].x; b=s[i].y;
			v=1;
			i++;
			while (i<k && (long long)a*s[i].y==(long long)b*s[i].x) v++, i++;
			nr+= v*(v-1)/2;
		}
	nr+=alfa*(alfa-1)/2;
	freopen ("trapez.out", "w", stdout);
	printf ("%d\n", nr);
	fclose(stdout);
	return 0;
}