Cod sursa(job #276436)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 11 martie 2009 10:22:07
Problema Triang Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 2.48 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

double round(double x)
	{
	x=x*1000000;
	x=floor(x+0.5);
	return x/1000000;
	}

int compara(struct pct a, struct pct b)
	{
	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(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; //sunt egale
	}

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=round(a); v[i].y=round(b);
		}
	}

//returneaza numarul de triunghiuri ce se pot forma
int numara()
	{
	int nr=0;
	int i,j;
	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=round(a.x*cos(M_PI/3)-a.y*sin(M_PI/3)+v[i].x);
			b.y=round(a.x*sin(M_PI/3)+a.y*cos(M_PI/3)+v[i].y);
			if(cbin(j+1,n,b)) nr++;
			//facem coordonatele pentru punctul cautat (rotit la dreapta)
			b.x=round(a.x*cos((-1)*M_PI/3)-a.y*sin((-1)*M_PI/3)+v[i].x);
			b.y=round(a.x*sin((-1)*M_PI/3)+a.y*cos((-1)*M_PI/3)+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;
}