Cod sursa(job #14845)

Utilizator victorsbVictor Rusu victorsb Data 9 februarie 2007 23:21:58
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 1024
#define x first
#define y second
#define mp make_pair

int n;
pair<int, int> punct[Nmax];

void citeste()
{
    int i, a1, a2, b1, b2;
    scanf("%d\n", &n);
    for (i=1; i<=n; ++i)
    {
        scanf("%d.%d %d.%d\n", &a1, &a2, &b1, &b2);
        punct[i] = mp(a1 * 100000 + a2 * 10, b1 * 100000 + b2 * 10);
    }
}

int cauta(pair<int, int> p)
{
    int st = 1, dr = n, mij;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (p < punct[mij])
            dr = mij - 1;
        else if (p > punct[mij])
            st = mij + 1;
        else 
            return 1;
    }
    return 0;
}

void solve()
{
    int i, j, ok, x0, y0, dx, dy, sol = 0;
    pair<int, int> p1, p2;
    sort(punct+1, punct+n+1);
    for (i=1; i<=n; ++i)
        for (j=i+1; j<=n; ++j)
        {
            x0 = (punct[i].x + punct[j].x) / 2;
            y0 = (punct[i].y + punct[j].y) / 2;
            dx = x0 - punct[i].x;
            if (dx < 0) dx = -dx;
            dy = y0 - punct[i].y;
            if (dy < 0) dy = -dy;
            if (punct[i].y < punct[j].y)
            {
                p1 = mp(x0 + dy, y0 - dx);
                p2 = mp(x0 - dy, y0 + dx);
            }
            else
            {
                p1 = mp(x0 - dy, y0 - dx);
                p2 = mp(x0 + dy, y0 + dx);
            }
            if (cauta(p1) && cauta(p2))
                ++sol;
        }
    printf("%d\n", sol / 2);
}

int main()
{
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
    citeste();
    solve();
    return 0;
}