Pagini recente » Cod sursa (job #385981) | Cod sursa (job #2210760) | Cod sursa (job #1463992) | Cod sursa (job #2348093) | Cod sursa (job #10688)
Cod sursa(job #10688)
#include <fstream>
#include <cmath>
using namespace std;
#define in "patrate3.in"
#define out "patrate3.out"
#define NMAX 1001
#define eps 1e-4
struct Punct {
double x;
double y;
} a[NMAX], aux;
int n, nrsol;
bool gasit = false;
double x_z, y_z, x_u, y_u, x2, y2, x3, y3;
double mijx, mijy;
double dx, dy, xa, ya;
void BS(int,int);
void Read();
void Solve();
void QSort( int, int );
void Write();
FILE *fout = fopen( out, "w" );
int main()
{
Read();
Solve();
Write();
fclose ( fout );
return 0;
}
void Read()
{
FILE *fin = fopen ( in, "r" );
fscanf( fin, "%d", &n );
int i;
double x, y;
for ( i = 1; i <= n; ++i )
{
fscanf( fin, "%lf%lf", &x, &y );
a[i].x = x;
a[i].y = y;
}
QSort( 1, n );
fclose ( fin );
}
/*
void Debug()
{
int i;
for ( i = 1; i <= n; ++i )
{
fprintf( fout, "%lf %lf\n", a[i].x, a[i].y );
}
}*/
//sorteaza perfect
void QSort( int st, int dr )
{
double pivot = a[st].x;
int i = st - 1, j = dr + 1;
do
{
do { i++; } while ( a[i].x < pivot||( fabs( a[i].x - pivot)<eps && a[i].y < a[st].y ) );
do { j--; } while ( a[j].x > pivot||( fabs( a[j].x - pivot)<eps && a[j].y > a[st].y ) );
if ( i <= j )
{
aux = a[i];
a[i] = a[j];
a[j] = aux;
}
} while ( i <= j );
if ( i < dr ) QSort ( i, dr );
if ( st < j ) QSort ( st, j );
}
void Solve()
{
int i, j;
for ( i = 1; i < n; ++i )
{
x_z = a[i].x;
y_z = a[i].y;
for ( j = i + 1; j <= n; ++j )
{
x_u = a[j].x;
y_u = a[j].y;
mijx = ( x_z + x_u ) / 2;
mijy = ( y_z + y_u ) / 2;
dx = fabs( mijx - x_z );
dy = fabs( mijy - y_z );
if ( y_z < y_u )
{
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;
}
xa = x2;
ya = y2;
gasit = false;
BS ( 1, n );
bool ok1 = gasit;
xa = x3;
ya = y3;
gasit = false;
BS ( 1, n );
bool ok2 = gasit;
if ( ok1 == true && ok2 == true ) nrsol++;
}
}
}
void Write()
{
fprintf( fout, "%d\n", nrsol );
}
void BS( int st, int dr )
{
int mij = (st + dr) >> 1;
if ( fabs( a[mij].x - xa ) < eps &&
fabs( a[mij].y - ya ) < eps )
{
gasit = true;
return;
}
if ( xa < a[mij].x )
{
if ( st < mij )
BS ( st, mij );
else gasit = false;
}
if ( xa > a[mij].x )
{
if ( mij + 1 < dr )
BS ( mij + 1, dr );
else gasit = false;
}
}