Cod sursa(job #530536)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 7 februarie 2011 22:09:46
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.b.y - s.a.y)*(t.b.x-t.a.x) == (s.b.x - s.a.x)*(t.b.y-t.a.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.b.y - s.a.y)*(t.b.x-t.a.x) <= (s.b.x - s.a.x)*(t.b.y-t.a.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;
}