Cod sursa(job #847186)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 3 ianuarie 2013 15:17:27
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;

ifstream fi ("trapez.in");
ofstream fo ("trapez.out");

const int dim = 1002;
int N, NM;
long long NR;
struct punct { long long x, y; } P[dim], M[dim*dim];

void cit ()
{
	fi >> N;
	for (int i = 1; i <= N; i++)
	{
		fi >> P[i].x >> P[i].y;
	}
}

int cmp (punct a, punct b)
{
	return (double)a.y / a.x < (double)b.y / b.x;
}

void pre ()
{
	int i, j;
	for (i = 1; i <= N; i++)
	{
		for (j = i + 1; j <= N; j++)
		{
			NM++;
			M[NM].x = P[i].x - P[j].x;
			M[NM].y = P[i].y - P[j].y;
		}
	}
	sort (M + 1, M + NM + 1, cmp);
}

void rez ()
{
	long long nr = 1;
	for (int i = 2; i <= NM; i++)
	{
		if (M[i].x * M[i-1].y == M[i-1].x * M[i].y)
			nr ++;
		else
		{
			if (nr > 1) NR += ((nr - 1) * nr) >> 1;
			nr = 1;
		}
	}
	if (nr > 1) NR += ((nr - 1) * nr) >> 1;
	fo << NR << '\n';
}

int main ()
{
	cit ();
	pre ();
	rez ();
	return 0;
}