Cod sursa(job #1290258)

Utilizator sulzandreiandrei sulzandrei Data 11 decembrie 2014 00:03:58
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const char iname[] = "patrate3.in";
const char oname[] = "patrate3.out";
#define MAX_N 1000
#define eps   1e-4
#define abs(z) ((z) < 0 ? (-(z)) : (z))

struct entry {
    double x;
    double y;
} ;
entry P[MAX_N];  int n;
void read_in()
{
    freopen(iname,"r", stdin);
    int i;
    scanf("%d",&n);
    for (i = 0; i < n; ++ i)
        scanf("%lf %lf",&P[i].x,&P[i].y);
}

int mycmp(entry z, entry w)
{
    if (abs(z.x - w.x) > eps)
        return z.x - w.x <= eps;
    return z.y - w.y <= eps;
}

int search(entry X[],int n,entry p) {
    int k;
    int stp;
    for (stp = 1; stp < n; stp *= 2)
        ;
    for (k = 0; stp > 0; stp /= 2)
        if (k + stp < n && mycmp(X[k + stp], p))
            k = k + stp;
    return (abs(p.x - X[k].x) < eps && abs(p.y - X[k].y) < eps);
}
int main(void) {
    read_in();
    sort(P, P + n, mycmp);
    int Res = 0;
    int i;
    int j;
    for (i = 0; i < n - 1; ++ i)
    {
        for (j = i + 1; j < n; ++ j)
        {
            entry m, f, g;
            m.x = (P[i].x + P[j].x) / 2.;
            m.y = (P[i].y + P[j].y) / 2.;
            double dx = abs(m.x - P[i].x);
            double dy = abs(m.y - P[i].y);
            if (P[i].y < P[j].y)
            {
                f.x = m.x + dy, f.y = m.y - dx;
                g.x = m.x - dy, g.y = m.y + dx;
            } else
            {
                f.x = m.x - dy, f.y = m.y - dx;
                g.x = m.x + dy, g.y = m.y + dx;
            }
            if (search(P, n, f) && search(P, n, g))
                Res ++;
        }
    }
    freopen(oname, "w", stdout);
    printf("%d\n", Res / 2);
    return 0;
}