Pagini recente » Cod sursa (job #613202) | Cod sursa (job #2651582) | Cod sursa (job #2508541) | Cod sursa (job #1023324) | Cod sursa (job #89051)
Cod sursa(job #89051)
/* O (N) memorie
* O (N^2 log N) timp
* Sortare abs/ord cu cautare binara
*/
#include <cstdio>
#include <math.h>
using namespace std;
#define FIN "patrate3.in"
#define FOUT "patrate3.out"
#define MAX_N 1 << 11
const double eps = 0.0001;
typedef struct
{
double x;
double y;
} point ;
int N, i;
int BEST; // solutia
point A[MAX_N >> 1];
int part (int st, int dr)
{
int i, j, s = 1;
i = st; j = dr;
while (i < j)
{
if (A[i].x - A[j].x > eps)
{
point d = A[i];
A[i] = A[j];
A[j] = d;
s = 1 - s;
}
if (fabs (A[i].x - A[j].x) < eps && A[i].y - A[j].y > eps)
{
point d = A[i];
A[i] = A[j];
A[j] = d;
s = 1 - s;
}
if (s) ++i; else --j;
}
return i;
}
void sort (int st, int dr)
{
if (st < dr)
{
int p = part (st, dr);
sort (st, p - 1);
sort (p + 1, dr);
}
}
int bsearch (point P)
{
int li, lf, m;
int f = 0; // gasit ?
li = 1; lf = N;
while (li <= lf)
{
m = (li + lf) >> 1;
if (double (fabs (P.x - A[m].x)) < eps && double (fabs (P.y - A[m].y)) < eps )
{
f = 1;
break ;
}
if (double (P.x - A[m].x) > eps) li = m + 1; // x > mid
if (double (A[m].x - P.x) > eps) lf = m - 1; // x < mid
if (double (fabs (P.x - A[m].x)) < eps) // x = mid
{
if (double (P.y - A[m].y) > eps) li = m + 1; // y > mid
if (double (A[m].y - P.y) > eps) lf = m - 1; // y < mid
}
}
return f;
}
void solve ( void )
{
int i, j;
point p0, p1; // diagonala fixata
point p2, p3; // punctele calculate
point mid;
for (i = 1; i <= N - 1; ++i)
for (j = i + 1; j <= N; ++j)
{
p0 = A[i]; p1 = A[j];
mid.x = double ((A[i].x + A[j].x) / 2);
mid.y = double ((A[i].y + A[j].y) / 2);
double dx = double ((fabs (mid.x - p0.x)));
double dy = double ((fabs (mid.y - p0.y)));
if (double ((p1.x - p0.x) * (p1.y - p0.y)) <= 0)
{
// left
p2.x = double (mid.x + dy);
p2.y = double (mid.y + dx);
p3.x = double (mid.x - dy);
p3.y = double (mid.y - dx);
if (bsearch (p2) && bsearch (p3)) ++ BEST;
}
else
{
// right
p2.x = double (mid.x - dy);
p2.y = double (mid.y + dx);
p3.x = double (mid.x + dy);
p3.y = double (mid.y - dx);
if (bsearch (p2) && bsearch (p3)) ++ BEST;
}
}
printf ("%d", int (BEST >> 1));
}
int main ()
{
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
scanf ("%d", &N);
for (i = 1; i <= N; ++i)
scanf ("%llf %llf", &A[i].x, &A[i].y);
sort (1, N);
solve ();
return 0;
}