Cod sursa(job #59558)

Utilizator scapryConstantin Berzan scapry Data 9 mai 2007 18:37:26
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <assert.h>
#include <stdio.h>
#include <map>
#include <utility>
using namespace std;

enum { maxn = 1024 };

int n;
int p[maxn][2];
int ans;
map< pair<int, int>, int > the;
typedef map< pair<int, int>, int >::iterator iter;

int euclid(int a, int b)
{
	int t;

	if(a > b)
	{
		t = a;
		a = b;
		b = t;
	}

	while(a)
	{
		assert(a <= b);
		assert(a > 0 && b > 0);
		
		t = a;
		a = b % a;
		b = t;
	}

	return b;
}

inline pair<int, int> fix(int x, int y)
{
	if(x == 0) y = 1;
	else if(y == 0) x = 1;
	else
	{
		//if(x < 0) x = -x;
		//if(y < 0) y = -y;

		int lcd = euclid(abs(x), abs(y));
		assert(lcd > 0);

		x /= lcd;
		y /= lcd;
	}

	return pair<int, int>(x, y);
}

void go()
{
	int i, j, x, y;
	pair<int, int> data;
	iter it;

	for(i = 0; i < n; i++)
		for(j = i + 1; j < n; j++)
		{
			x = p[i][0] - p[j][0];
			y = p[i][1] - p[j][1];

			data = fix(x, y);
			it = the.find(data);

			if(it != the.end()) //found
			{
				ans += it->second;
				it->second++;
			}
			else //new one
			{
				the[data] = 1;
			}
		}
}

int main()
{
	int i;
	FILE *f = fopen("trapez.in", "r");
	if(!f) return 1;

	fscanf(f, "%d", &n);
	for(i = 0; i < n; i++)
		fscanf(f, "%d%d", &p[i][0], &p[i][1]);

	fclose(f);
	f = fopen("trapez.out", "w");
	if(!f) return 1;

	go();

	fprintf(f, "%d\n", ans);
	fclose(f);
	return 0;
}