Cod sursa(job #531462)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 9 februarie 2011 18:36:59
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <algorithm>
using namespace std;

struct punct
{
	int x,y;
};

struct segment
{
	punct a,b;
};

const int N = 1001;
const double INF = 10000000000.0;

punct pct[N]; int n;
segment sgm[N*N]; int nsgm;
long long nr_trap;

void citire()
{
	scanf("%i",&n);
	for (int i = 1; i <= n; ++i)
		scanf("%i%i",&pct[i].x,&pct[i].y);
}

void creare_segmente()
{
	for (int i = 1; i <= n; ++i)
		for (int j = i+1; j <= n; ++j)
		{
			sgm[++nsgm].a = pct[i];
			sgm[nsgm].b = pct[j];
		}
}

inline double panta (segment s)
{
	if (s.a.x == s.b.x)
		return INF;
	return (double)(s.a.y - s.b.y)/(s.a.x - s.b.x);
}

bool panta_crescatoare(segment s, segment t)
{
	return panta(s) <= panta(t);
}

void numarare_trapeze()
{
	int l_sir_pnt_egale = 1;
	for (int i = 2; i <= nsgm; ++i)
		if (panta(sgm[i-1]) == panta(sgm[i]))
			++l_sir_pnt_egale;
		else
		{
			nr_trap += l_sir_pnt_egale * (l_sir_pnt_egale - 1)/2;
			l_sir_pnt_egale = 1;
		}
	nr_trap += l_sir_pnt_egale * (l_sir_pnt_egale - 1)/2;  //n(n-1)/2
}

int main()
{
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	citire();
	creare_segmente();
	sort(sgm+1,sgm+nsgm+1,panta_crescatoare);
	numarare_trapeze();
	printf("%i",nr_trap);
	return 0;
}