Pagini recente » Cod sursa (job #1016296) | Cod sursa (job #1379769) | Cod sursa (job #2123760) | Cod sursa (job #823326) | Cod sursa (job #11573)
Cod sursa(job #11573)
#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(double,double);
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 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 ( xa, ya );
bool ok1 = gasit;
xa = x3;
ya = y3;
gasit = false;
BS ( xa, ya );
bool ok2 = gasit;
if ( ok1 == true && ok2 == true )
{
nrsol++;
}
}
}
}
void Write()
{
fprintf( fout, "%d\n", (nrsol>>1));
}
void BS(double xa, double ya)
{
int bl = 1,br = n, bm;//asta cred ca e buna
while ( bl <= br )
{
bm = (br+bl)>>1;
if ( a[bm].x - xa >= eps ) br = bm - 1;
else
{
if ( xa - a[bm].x >= eps ) bl = bm + 1;
else if ( fabs( a[bm].x - xa ) < eps )
{
if ( a[bm].y - ya >= eps )
{
br = bm - 1;
}
else if ( ya - a[bm].y >= eps )
{
bl = bm + 1;
}
if ( fabs(a[bm].y - ya ) < eps ) gasit = true, bl = br + 1;
}
}
}
}