Cod sursa(job #1282480)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 4 decembrie 2014 11:39:24
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 2.46 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

const int NMAX = 1005;
const int BASE = 103;
const int MOD = 100009;

int N, M, i, j, r, X0, Y0, X1, Y1, X2, Y2, X3, Y3, dx, dy, mijx, mijy, SOL, ok;

struct Point
{
    int x, y;
};
Point P[NMAX];

char S[100];

vector<pair<int, int> > V[MOD];

int main()
{
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);

    scanf("%d", &N);

    for(i = 1; i <= N; i++)
    {
        scanf("%s", S + 1);
        M = strlen(S + 1);
        for(j = 1; j <= M; j++) if(S[j] >= '0' && S[j] <= '9') P[i].x = P[i].x * 10 + S[j] - '0';
        if(S[1] == '-') P[i].x *= -1;

        scanf("%s", S + 1);
        M = strlen(S + 1);
        for(j = 1; j <= M; j++) if(S[j] >= '0' && S[j] <= '9') P[i].y = P[i].y * 10 + S[j] - '0';
        if(S[1] == '-') P[i].y *= -1;

        P[i].x *= 2;
        P[i].y *= 2;

        r = (1LL * BASE * (abs(P[i].x)) + (abs(P[i].y))) % MOD;
        V[r].push_back(make_pair(P[i].x, P[i].y));
    }

    for(i = 1; i <= N; i++)
        for(j = 1; j <= N; j++)
            if(P[i].y < P[j].y && P[i].x <= P[j].x)
            {
                X0 = P[i].x;
                Y0 = P[i].y;
                X1 = P[j].x;
                Y1 = P[j].y;
                mijx = X0 + (X1 - X0) / 2;
                mijy = Y0 + (Y1 - Y0) / 2;
                dx = abs(mijx - X0);
                dy = abs(mijy - Y0);
                X2 = mijx + dy;
                Y2 = mijy - dx;
                X3 = mijx - dy;
                Y3 = mijy + dx;

                r = (1LL * BASE * (abs(X2)) + abs(Y2)) % MOD;
                ok = 0;
                for(vector<pair<int, int> >::iterator it = V[r].begin(); it != V[r].end(); it++)
                    if(it->first == X2 && it->second == Y2)
                    {
                        ok = 1;
                        break;
                    }
                if(!ok) continue;

                r = (1LL * BASE * (abs(X3)) + abs(Y3)) % MOD;
                ok = 0;
                for(vector<pair<int, int> >::iterator it = V[r].begin(); it != V[r].end(); it++)
                    if(it->first == X3 && it->second == Y3)
                    {
                        ok = 1;
                        break;
                    }
                if(!ok) continue;

                SOL++;
            }

    printf("%d\n", SOL);

    return 0;
}