Pagini recente » Cod sursa (job #1747298) | Cod sursa (job #1107501) | Cod sursa (job #501913) | Cod sursa (job #1389306) | Cod sursa (job #36540)
Cod sursa(job #36540)
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define M 0.001
typedef struct punct { double x,y; } punct;
punct x[1600];
int n;
long nr;
double xx1,xx2,yy1,yy2;
int cmp(const void *x,const void *y){
punct *xx=(punct *)x,*yy=(punct *)y;
if(xx->x - yy->x > M ) return 1;
if(xx->x - yy->x < -M ) return -1;
if(xx->y - yy->y > M) return 1;
if(xx->y - yy->y <-M ) return -1;
return 0;
}
void READ(){
FILE *f;
int i;
f=fopen("triang.in","r");
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf %lf",&x[i].x,&x[i].y);
fclose(f);
}
void calcul(double xa,double ya,double xb,double yb){
double a,b,A,B;
b=yb-ya;
a=xb-xa;
B=(xb*xb-xa*xa+yb*yb-ya*ya)/2;
A=xa*yb-xb*ya+((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb) ) /2*sqrt(3);
xx1=(A*b+B*a)/(a*a+b*b);
yy1=(-A*a+B*b)/(a*a+b*b);
A=xa*yb-xb*ya-((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb))/2*sqrt(3);
xx2=(A*b+B*a)/(a*a+b*b);
yy2=(-A*a+B*b)/(a*a+b*b);
}
int caut(long xx, long yy){
int p,i;
for(p=1;p<=n;p<<=1);
for(i=0;p;p>>=1){
if(i+p<=n && ( xx>=(long)(x[i+p].x*1000) || (xx==(long)(x[i+p].x*1000) && yy>=(long)(x[i+p].y*1000)) ))
i+=p;
}
if( xx-(long)(x[i].x*1000)>=-1 && xx-(long)(x[i].x*1000)<=1 && yy-(long)(x[i].y*1000)<=1 && yy-(long)(x[i].y*1000)>=-1 ) return 1;
return 0;
}
void SOLVE(){
int i,j,ok,ii,jj;
long xx,yy;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++){
calcul(x[i].x,x[i].y,x[j].x,x[j].y);
xx=1000*xx1;
yy=1000*yy1;
ok=0;
for(ii=0;!ok && ii<=0;ii++){
for(jj=0;!ok && jj<=0;jj++)
ok=caut(xx+ii,yy+jj);
}
nr+=ok;
xx=1000*xx2;
yy=1000*yy2;
ok=0;
for(ii=0;!ok && ii<=0;ii++){
for(jj=0;!ok && jj<=0;jj++)
ok=caut(xx+ii,yy+jj);
}
nr+=ok;
}
}
void PRINT(){
FILE *g;
g=fopen("triang.out","w");
fprintf(g,"%ld",nr/3);
fclose(g);
}
int main(){
READ();
qsort(x+1,n,sizeof(punct),cmp);
SOLVE();
PRINT();
return 0;
}