Pagini recente » Cod sursa (job #2146887) | Cod sursa (job #202785) | Cod sursa (job #1489197) | Cod sursa (job #1844263) | Cod sursa (job #276464)
Cod sursa(job #276464)
#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*10000000;
x=floor(x+0.5);
return x/10000000;
}
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;
}