Pagini recente » Cod sursa (job #803639) | Cod sursa (job #326660) | Cod sursa (job #1536227) | Cod sursa (job #1031420) | Cod sursa (job #277215)
Cod sursa(job #277215)
#include<stdio.h>
#include<math.h>
#define infile "triang.in"
#define outfile "triang.out"
#define nmax 1501
#define hmax (2*10*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;
}