Cod sursa(job #530533)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 7 februarie 2011 22:08:31
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <algorithm>
using namespace std;

struct punct
{
	int x,y;
};

struct segment
{
	punct a,b;
};

const int N = 1001;

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 bool panta_egala(segment s, segment t)
{
	return (s.a.y - s.b.y)*(t.a.x-t.b.x) == (s.a.x - s.b.x)*(t.a.y-t.b.y);
}

bool panta_crescatoare(segment s, segment t)//nush daca conteaza (y1-y2)/(x1-x2) sau (y2-y1)/(x2-x1)
{//mezi ori extremi
	if ((s.a.y - s.b.y)*(t.a.x-t.b.x) <= (s.a.x - s.b.x)*(t.a.y-t.b.y))
		return true;
	return false;
}

void numarare_trapeze()
{
	int l_sir_pnt_egale = 1;
	for (int i = 2; i <= nsgm; ++i)
		if (panta_egala(sgm[i-1],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;
}