Pagini recente » Cod sursa (job #2825653) | Cod sursa (job #3285801) | Cod sursa (job #1115305) | Cod sursa (job #3123697) | Cod sursa (job #1321105)
#include<stdio.h>
#include<math.h>
#define eps 0.001
struct point
{
double x,y;
};
int n;
int f[1002];
point v[1002];
void read()
{
freopen("patrate3.in","r",stdin);
freopen("patrate3.out","w",stdout);
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
}
int part(int st, int dr)
{
int i,j,m;
point aux,p;
m=(st+dr)>>1;
p=v[m];
i=st-1;
j=dr+1;
while(1)
{
do{++i;}while((p.x-v[i].x)>=eps || ((fabs(p.x-v[i].x)<eps) && (p.y-v[i].y>=eps)));
do{--j;}while((v[j].x-p.x)>=eps || ((fabs(p.x-v[j].x)<eps) && (v[j].y-p.y>=eps)));
if(i<j)
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
}
else
return j;
}
}
void quick(int st, int dr)
{
int p;
if(st<dr)
{
p=part(st,dr);
quick(st,p);
quick(p+1,dr);
}
}
int cautare(point x)
{
int st,dr,m;
st=1;
dr=n;
while(st!=dr)
{
m=(st+dr)>>1;
if(((v[m].x-x.x)>=eps) || ((fabs(v[m].x-x.x)<eps) && (v[m].y-x.y)>=eps))
dr=m;
else
st=m+1;
}
return st-1;
}
void rez()
{
int i,j,patrate=0,poz1,poz2;
point m,p2,p3,d;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
m.x=(v[i].x+v[j].x)*0.5;
m.y=(v[i].y+v[j].y)*0.5;
d.x=fabs(m.x-v[i].x);
d.y=fabs(m.y-v[i].y);
if((v[j].y-v[i].y)>=eps)
{
p2.x=m.x+d.y;
p2.y=m.y-d.x;
p3.x=m.x-d.y;
p3.y=m.y+d.x;
}
else
{
//x2 = mijx - dy, y2 = mijy - dx, x3 = mijx + dy iar y3 = mijy + dx.
p2.x=m.x-d.y;
p2.y=m.y-d.x;
p3.x=m.x+d.y;
p3.y=m.y+d.x;
}
poz1=cautare(p2);
poz2=cautare(p3);
if((fabs(v[poz1].x-p2.x)<eps) && (fabs(v[poz1].y-p2.y)<eps))
if((fabs(v[poz2].x-p3.x)<eps) && (fabs(v[poz2].y-p3.y)<eps))
if(cautare(p2) && cautare(p3))
{
if(f[i]==0 && f[j]==0 && f[poz1]==0 && f[poz2]==0)
{
patrate++;
f[i]=f[j]=f[poz1]=f[poz2]=1;
}
}
}
printf("%d\n",patrate);
}
int main()
{
read();
quick(1,n);
rez();
return 0;
}