Cod sursa(job #277234)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 11 martie 2009 16:37:45
Problema Triang Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<stdio.h>
#include<math.h>
#define infile "triang.in"
#define outfile "triang.out"
#define nmax 1501
#define hmax (2*100*1001)
struct lista
	{
	int p; //pozitia fratelui
	double x,y; //coordonatele punctului
	} l[nmax]; //lista in care vom avea punctele
int h[hmax]; //tabela HASH
int n; //numarul de puncte

double modul(double x)
	{
	if(x<0) return (-1)*x; return x;
	}

int cod(double x, double y)
	{
	return (floor(modul(x))+floor(modul(y))); //partea intreaga
	}

int compara(double a, double b, double x, double y)
	{
	//ne intereseaza doar daca sunt egale
	if(modul(a-x)<0.001) //inseamna ca abscisa este egala
		if(modul(b-y)<0.001) return 1; //sunt egale
	return 0; //inseamna k nu sunt egale
	}

int exista(double a, double b)
	{
	int p;
	int x=cod(a,b); //codul din tabela
	for(p=h[x];p;p=l[p].p) //trecem la toate punctele din lista asta
		;//if(compara(a,b,l[p].x,l[p].y)) return 1; //daca punctul de coordonate ab==cu punctul p
	return 0; //inseamna k nu a fost gasit
	}

void add(int i)
	{
	int x=cod(l[i].x,l[i].y); //genereaza codul hash
	l[i].p=h[x]; h[x]=i; //il adaugam in tabela hash
	}

void citire()
	{
	int i;
	scanf("%d\n",&n); //numarul de puncte
	for(i=1;i<=n;i++)
		{
		scanf("%lf %lf",&l[i].x,&l[i].y); //citim coordonatele punctelor
		add(i); //il adaugam in tabela hash
		}
	}

//numara si returneaza numarul de triunghiuri ce se pot forma
int numara()
	{
	int nr=0; //aici vom calcula numarul de triunghiuri
	int i,j;
	double x,y,a,b;
	double sp=sin(M_PI/3); //sinus pt rotatie la stanga
	double cp=cos(M_PI/3); //cosinus pt rotatie la stanga
	double sn=sin((-1)*M_PI/3); //sinus pt rotatie la dreapta
	double cn=cos((-1)*M_PI/3); //cosinus pt rotatie la dreapta
	for(i=1;i<n;i++)
		for(j=i+1;j<n;j++)
			{
			//translatam cele doua puncte
			x=l[j].x-l[i].x;
			y=l[j].y-l[i].y;
			//coordonatele punctului ce form tr. echil in stanga
			a=x*cp-y*sp+l[i].x;
			b=x*sp+y*cp+l[i].y;
			if(exista(a,b)) nr++; //daca exista punctul
			//coordonatele punctului ce form tr. echil in dreapta
			a=x*cn-y*sn+l[i].x;
			b=x*sn+y*cn+l[i].y;
			if(exista(a,b)) nr++; //daca exista punctul
			}
	return nr;
	}

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

citire();
printf("%d",numara());

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