Cod sursa(job #276709)
#include<stdio.h>
#include<math.h>
#define infile "triang.in"
#define outfile "triang.out"
#define nmax 1501
struct pct
{
int x,y; //coordonate pt pct
} v[nmax]; //vectorul cu punctele
int n; //numarul de puncte
int trunc(double x)
{
x=x*10000;
return floor(x);
}
double round(double x)
{
x=x;
x=floor(x+0.5);
return x;
}
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
*/
if(a.x>b.x || (a.x==b.x && a.y>b.y)) return 1; //e mai mic al doilea
if(a.x<b.x || (a.x==b.x && a.y<b.y)) return -1; //e mai mic primul
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=trunc(a); v[i].y=trunc(b);
}
}
//returneaza numarul de triunghiuri ce se pot forma
int numara()
{
int nr=0;
int i,j;
double x,y;
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 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
x=v[j].x-v[i].x;
y=v[j].y-v[i].y;
//facem coordonatele pentru punctul cautat (rotit la stanga)
b.x=round(x*cp-y*sp+v[i].x);
b.y=round(x*sp+y*cp+v[i].y);
if(cbin(j+1,n,b)) nr++;
//facem coordonatele pentru punctul cautat (rotit la dreapta)
b.x=round(x*cn-y*sn+v[i].x);
b.y=round(x*sn+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;
}