Cod sursa(job #276603)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 11 martie 2009 11:30:15
Problema Triang Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 2.55 kb
#include<stdio.h>
#include<math.h>
#define infile "triang.in"
#define outfile "triang.out"
#define nmax 1501
struct pct
	{
	double x,y; //coordonate pt pct
	} v[nmax]; //vectorul cu punctele
int n; //numarul de puncte

int compara(struct pct a, struct pct b)
	{
	if(!(fabs(a.x-b.x)<0.001))
		{ //sunt diferite
		if(a.x<b.x) return -1; //e mai mi cel din partea stanga
		if(a.x>b.x) return 1; //e mai mic al 2-lea
		}
	if(fabs(a.y-b.y)<0.001) return 0; //sunt egale
	if(a.y<b.y) return -1; //e mai mic primul
	if(a.y>b.y) return 1; //e mai mic al 2-lea
	return 0; //sigur nu se va ajunge aici :P
	}

int divide(int p, int q)
	{
	struct pct x=v[p]; //pct-ul ce trebuie plasat corect
	while(p<q)
		{
		while(p<q && compara(x,v[q])<=0) q--;
		v[p]=v[q];
		while(p<q && compara(x,v[p])>=0) p++;
		v[q]=v[p];
		}
	v[p]=x; //plasam corect
	return p; //ii returnam pozitia
	}

//sorteaza intervalul [p,q]
void qsort(int p, int q)
	{
	int m=divide(p,q); //plasam p corect
	if(p<m-1) qsort(p,m-1); //sortam partea stanga
	if(m+1<q) qsort(m+1,q); //sortam partea dreapta
	}

//cauta punctul de coord x, in intervalul [p,q]
int cbin(int p, int q, struct pct x)
	{
	int m,c;
	while(p<=q)
		{
		m=(p+q)/2;
		c=compara(v[m],x);
		if(!c) return 1; //am gasit
		if(c<0) p=m+1; //cautam doar in partea dreapta
		else q=m-1; //cautam in partea stanga
		}
	return 0; //nu l-am gasit
	}

void citire()
	{
	int i;
	double a,b;
	scanf("%d\n",&n);
	for(i=1;i<=n;i++) //citim coordonatele fiecarui pct
		{
		scanf("%lf %lf\n",&a,&b);
		v[i].x=a; v[i].y=b;
		}
	}

//returneaza numarul de triunghiuri ce se pot forma
int numara()
	{
	int nr=0;
	int i,j;
	double cp=cos(M_PI/3); //cos pozitiv
	double cn=cos((-1)*M_PI/3); //cos negativ
	double sp=sin(M_PI/3); //sin pozitiv
	double sn=sin((-1)*M_PI/3); //sin negativ
	struct pct a,b;
	for(i=1;i<=n;i++)
		for(j=i+1;j<n;j++)
			{
			//formam coordonatele punctului care ar forma cu cele doua punctu un tr. echil.
			//translatam punctele
			a.x=v[j].x-v[i].x;
			a.y=v[j].y-v[i].y;
			//facem coordonatele pentru punctul cautat (rotit la stanga)
			b.x=a.x*cp-a.y*sp+v[i].x;
			b.y=a.x*sp+a.y*cp+v[i].y;
			if(cbin(j+1,n,b)) nr++;
			//facem coordonatele pentru punctul cautat (rotit la dreapta)
			b.x=a.x*cn-a.y*sn+v[i].x;
			b.y=a.x*sn+a.y*cn+v[i].y;
			if(cbin(j+1,n,b)) nr++;
			}
	return nr;
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire();
qsort(1,n); //sortam punctele
printf("%d",numara());

fclose(stdin);
fclose(stdout);
return 0;
}