Cod sursa(job #284858)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 22 martie 2009 00:22:29
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int N, nr, cnt;

struct segment
{
	int x, y;
} v[1000005], a[1005];
	
int cmp(const segment &x, const segment &y)
{
	if (x.x == y.x) return x.y < y.y;
	return x.x < y.x;
}

int cmmdc(int x, int y)
{
	if (!y) return x;
	else return cmmdc(y, x % y);
}

int ab(int x) {return x > 0 ? x : -x;}
int main()
{
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	
	int i, j, x;
	scanf("%d", &N);
	
	for (i = 1; i <= N; i++) scanf("%d %d", &a[i].x, &a[i].y);
	sort(a + 1, a + N + 1, cmp);
	
	for (i = 1; i < N; i++)
		for (j = i + 1; j <= N; j++)
		{
			v[nr].x = a[j].x - a[i].x;
			v[nr].y = a[j].y - a[i].y;
			if (v[nr].x && v[nr].y)
			{				
				x = cmmdc(ab(v[nr].x), ab(v[nr].y));
				v[nr].x /= x; v[nr].y /= x;
			}
			if (!v[nr].y) { v[nr].x = v[nr].y = -1;}
			if (!v[nr].x) { v[nr].x = v[nr].y = -2;}
			nr++;
		}
	sort(v, v + nr, cmp);
	
	i = j = 0;
	while (i < nr)
	{
		j = i;
		while ((v[i].x == v[j].x && v[i].y == v[j].y) || (v[i].x == 0 && v[j].x == 0)) j++;
		x = j - i;
		cnt += (x * (x - 1)) / 2;
		i = j;
	}
	printf("%d\n", cnt);
	return 0;
}