Cod sursa(job #448412)

Utilizator ChallengeMurtaza Alexandru Challenge Data 3 mai 2010 18:25:24
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

const char InFile[]="trapez.in";
const char OutFile[]="trapez.out";
const int MaxN=1005;
const double EPS=1e-10;

struct POINT
{
	int x,y;
};

inline bool same_points(POINT a, POINT b)
{
	return a.x==b.x && a.y==b.y;
}

inline int absi(int a)
{
	if(a>0)return a;
	return -a;
}

int cmmdc(int a, int b)
{
	if(b==0 || a==0)return 1;
	a=absi(a);
	b=absi(b);
	int r=a%b;
	while(r)
	{
		a=b;
		b=r;
		r=a%b;
	}
	return b;
}

inline POINT simplify(POINT a)
{
	int c=cmmdc(a.x,a.y);
	a.x=a.x/c;
	a.y=a.y/c;
	return a;
}

bool pcmp(POINT a, POINT b)
{
	if(a.x<b.x)return true;
	if(a.x>b.x)return false;
	if(a.y<b.y)return true;
	if(a.y>b.y)return false;
	return false;
}

ifstream fin(InFile);
ofstream fout(OutFile);
POINT p[MaxN];
int n,nr,l,OX,OY;
vector<POINT> v;

int main()
{
	fin>>n;
	for(register int k=0;k<n;++k)
	{
		fin>>p[k].x>>p[k].y;
	}
	fin.close();
	
	for(register int i=0;i<n;++i)
	{
		for(register int j=0;j<n;++j)
		{
			if(i!=j)
			{
				POINT P;
				P.x=p[i].x-p[j].x;
				P.y=p[i].y-p[j].y;
				if(P.x==0)++OX;
				else if(P.y==0)++OY;
				else
				{
					v.push_back(simplify(P));
				}
			}
		}
	}
	

	sort(v.begin(),v.end(),pcmp);
	
	l=1;
	for(register int i=1;i<(int)v.size();++i)
	{
		if(same_points(v[i],v[i-1]))
		{
			++l;
		}
		else
		{
			nr+=((l-1)*l)/2;
			l=1;
		}
	}
	OX/=2;
	OY/=2;
	nr+=((l-1)*l)/2;
	
	fout<<nr/2+((OX-1)*OX)/2+((OY-1)*OY)/2;
	fout.close();
	return 0;
}