Pagini recente » Cod sursa (job #2685970) | Cod sursa (job #2774939) | Cod sursa (job #1842025) | Cod sursa (job #3206726) | Cod sursa (job #8254)
Cod sursa(job #8254)
#include <stdio.h>
#include <math.h>
#define in "patrate3.in"
#define out "patrate3.out"
#define eps 0.0001
#define dim 1001
struct punct {
double x, y;
} a[dim];
int n;
void Qsort(int,int);
int BinaryS(double i, double j);
int main()
{
int t=0;
double x0, y0, x1, y1, x2, y2, x3, y3, mijx, mijy, dx, dy;
double x_, y_;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d",&n);
for ( int i = 1; i <= n; i++ )
{
scanf("%lf%lf",&x_,&y_);
a[i].x = x_;
a[i].y = y_;
}
Qsort(1,n);
/* for ( int i = 1; i <= n; i++ )
{
printf("%lf %lf\n",a[i].x,a[i].y);
}*/
for ( int i = 1; i < n; i++ )
{
for ( int j = i+1; j <= n; j++ )
{
x0 = a[i].x; y0 = a[i].y;
x1 = a[j].x; y1 = a[j].y;
mijx = (x0 + x1) / 2; mijy = (y0 + y1) / 2;
dx = fabs(mijx - x0); dy = fabs(mijy - y0);
if ( y0 < y1 )
{
x2 = mijx + dy; y2 = mijy - dx;
x3 = mijx - dy; y3 = mijy + dx;
}
else
{
x2 = mijx - dy; y2 = mijy - dx;
x3 = mijx + dy; y3 = mijy + dx;
}
// printf("%lf %lf %lf %lf %d %d\n", x2,y2, x3, y3, BinaryS(x2,y2), BinaryS(x3,y3));
if ( BinaryS(x2,y2) == 1 && BinaryS(x3,y3) ) t += 1;
}
}
printf("%d",t/2);
}
void Qsort(int st, int dr)
{
int i = st-1;
int j = dr+1;
double piv = a[st].x;
double piv2 = a[st].y;
while ( i <= j )
{
do { i++; } while ( (piv - a[i].x) >= eps );// || ( (piv-a[i].x) < eps && (piv2-a[i].y) > eps ));
do { j--; } while ( (a[j].x - piv) >= eps );// || ( (a[j].x-piv) < eps && (piv2-a[j].y) > eps ));
if ( i <= j )
{
punct aux = a[i];
a[i] = a[j];
a[j] = aux;
}
}
if ( st < j ) Qsort(st,j);
if ( i < dr ) Qsort(i,dr);
}
int BinaryS(double i, double j)
{
int st = 1;
int dr = n;
int mij = (st+dr)/2;
int ok = 0;
while ( st <= dr )
{
mij = (st+dr)/2;
if ( a[mij].x - i > eps )
{
dr = mij-1;
}
else
{
if ( i - a[mij].x > eps )
{
st = mij+1;
}
else
if ( a[mij].x - i < eps )
{
if ( a[mij].y - j > eps )
{
dr = mij-1;
}
else
if ( j-a[mij].y > eps )
{
st = mij+1;
}
if ( a[mij].y - j < eps ) ok = 1, st = dr+1;
}
}
}
return ok;
}