Pagini recente » Cod sursa (job #441676) | Cod sursa (job #3285963) | Cod sursa (job #1017262) | Cod sursa (job #1592352) | Cod sursa (job #75145)
Cod sursa(job #75145)
# include <stdio.h>
# include <math.h>
typedef struct PUNCT {double x,y;};
const long int MAXN=1500;
PUNCT pct[MAXN+1];
const double EPSILON=0.0001;
long int n,sol;
void citire()
{
FILE *f=fopen("triang.in","r");
fscanf(f,"%ld",&n);
long int i;
for (i=1;i<=n;i++)
fscanf(f,"%lf%lf",&pct[i].x,&pct[i].y);
fclose(f);
}
double dist (PUNCT a, PUNCT b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double modul (double a) { if (a>=0) return a; return -a;}
double sign (double a) {if (a>=0) return 1; return -1;}
void quick(long int li, long int lf)
{
long int i=li,j=lf,ii=0,jj=-1,auxi;
PUNCT aux;
while (i<j)
{
if ((pct[i].x-pct[j].x)>EPSILON||(pct[i].x-pct[j].x<+EPSILON&&pct[i].y-pct[j].y>EPSILON))
{
aux=pct[i];pct[i]=pct[j];pct[j]=aux;
auxi=ii;ii=-jj;jj=-auxi;
}
i+=ii;j+=jj;
}
if (i-li>1) quick(li,i-1);
if (lf-i>1) quick(i+1,lf);
}
int search(double x, double y)
{
long int li=1,lf=n,m;
while (li<=lf)
{
m=(li+lf)/2;
if (modul(pct[m].x-x)<=EPSILON&&modul(pct[m].y-y)<=EPSILON) return 1;
if (pct[m].x>x||(modul(pct[m].x-x)<=EPSILON&&pct[m].y>y)) lf=m-1;
else li=m+1;
}
return 0;
}
void calculeaza()
{
long int i,j;
PUNCT m,a,b;
double rad,l;
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
{
m.x=(pct[i].x+pct[j].x)/2;
m.y=(pct[i].y+pct[j].y)/2;
a=pct[i];b=pct[j];
l=dist(pct[i],pct[j]);
rad=sqrt(3)/2;
if (modul(a.x-b.x)<=EPSILON)
{
sol+=search(m.x-rad*l,m.y);
sol+=search(m.x+rad*l,m.y);
}
else if (modul(a.y-b.y)<=EPSILON)
{
sol+=search(m.x,m.y+rad*l);
sol+=search(m.x,m.y-rad*l);
}
else
{
if (sign((a.y-b.y)/(a.x-b.x))==1)
{
sol+=search(m.x-modul(b.y-a.y)*rad,m.y+modul(b.x-a.x)*rad);
sol+=search(m.x+modul(b.y-a.y)*rad,m.y-modul(b.x-a.x)*rad);
}
else
{
sol+=search(m.x-modul(b.y-a.y)*rad,m.y-modul(b.x-a.x)*rad);
sol+=search(m.x+modul(b.y-a.y)*rad,m.y-modul(b.x-a.x)*rad);
}
}
}
}
void scrie()
{
FILE *g=fopen("triang.out","w");
fprintf(g,"%ld\n",sol/3);
fcloseall();
}
int main()
{
citire();
quick(1,n);
calculeaza();
scrie();
return 0;
}