Cod sursa(job #93980)

Utilizator stef2nStefan Istrate stef2n Data 21 octombrie 2007 01:30:19
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <map>
using namespace std;

#define NMAX 1005
struct point {int x,y;};

int N;
point P[NMAX];
long long sol=0;
map < pair<int,int>, int > M; // in map se insereaza tangentele tuturor unghiurilor

void read_data()
{
	scanf("%d",&N);
	for(int i=0; i<N; i++)
		scanf("%d %d",&P[i].x,&P[i].y);
}

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

void add(point A, point B)
{
	int x,y,div;
	x=B.x-A.x;
	y=B.y-A.y;
	if(!x)
	{
		y=1;
		div=1;
	}
	else
		div=cmmdc(abs(x),y);
	x/=div;
	y/=div;
	M[make_pair(x,y)]++;
}

void solve()
{
	for(int i=0; i<N; i++)
		for(int j=i+1; j<N; j++)
			if(P[j].y>=P[i].y)
				add(P[i],P[j]);
			else
				add(P[j],P[i]);
	for(map < pair<int,int>, int > :: iterator it=M.begin(); it!=M.end(); ++it)
		sol += (long long)it->second*(it->second-1)/2;
//	for(map < pair<int,int>, int > :: iterator it=M.begin(); it!=M.end(); ++it)
//		cerr<<it->first.first<<" "<<it->first.second<<" "<<it->second<<endl;
}


int main()
{
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	read_data();
	solve();
	printf("%Ld\n",sol);
	return 0;
}