Cod sursa(job #448046)

Utilizator darrenRares Buhai darren Data 2 mai 2010 15:01:20
Problema Trapez Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

typedef int int64;

struct trio
{
	int64 x, y;
	int64 z;
};

trio make_trio( int64 x, int64 y, int64 z )
{
	trio aux;
	aux.x = x, aux.y = y, aux.z = z;
	return aux;
}
bool operator == ( trio a, trio b )
{
	return a.x == b.x && a.y == b.y && a.z == b.z;
}

void read();
void write();
void comp();
inline int64 cmmdc( int64 a, int64 b )
{
	if ( b == 0 )
		return a;
	return cmmdc( b, a % b );
}
inline int64 absol( int64 a )
{
	return a < 0 ? a * -1 : a;
}
inline bool cmp( const trio& a, const trio& b )
{
	if ( a.z != b.z )
		return a.z < b.z;
	if ( a.x != b.x )
		return a.x < b.x;
	return a.y <= b.y;
}

int64 n, cnt;
vector<trio> pct;
vector<trio> pnt;

int main()
{
	read();
	comp();
	write();
	return 0;
}

void read()
{
	ifstream fin( "trapez.in" );
	fin >> n;
	pct.resize( n );
	for ( int64 i = 0; i < n; ++i )
		fin >> pct[i].x >> pct[i].y;
	fin.close();
}

void write()
{
	ofstream fout( "trapez.out" );
	fout << cnt;
	fout.close();
}

void comp()
{
	for ( int64 i = 0; i < n - 1; ++i )
		for ( int64 j = i + 1; j < n; ++j )
		{
			int64 ax1 = pct[i].y - pct[j].y,
			    ax2 = pct[i].x - pct[j].x;
			int64 semn;
			
			if ( ( ax1 >= 0 && ax2 >= 0 ) || ( ax1 < 0 && ax2 < 0 ) )
				semn = 0;
			else
				semn = 1;
			ax1 = absol(ax1), ax2 = absol(ax2);
			
			if ( ax1 != 0 && ax2 != 0 )
			{
				int64 d = cmmdc( ax1, ax2 );
				ax1 /= d, ax2 /= d;
			}
			else
			{
				if ( ax1 == 0 )
					ax1 = ax2 = 0;
				else
					ax1 = ax2 = -1;
			}
			
			pnt.push_back( make_trio( ax1, ax2, semn ) );
		}
	sort( pnt.begin(), pnt.end(), cmp );
	
	trio old;
	old.x = old.y = -1;
	int64 now = 1;
	for ( int64 i = 0; i < (int64) pnt.size(); ++i )
		if ( pnt[i] == old )
			++now;
		else
		{
			cnt += now * ( now - 1 ) / 2;
			old = pnt[i];
			now = 1;
		}
}