Cod sursa(job #1167017)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 4 aprilie 2014 10:47:24
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;

#define pi pair<int,int>
#define x first
#define y second
#define mp make_pair
#define MOD 666013
#define NMAX 1005
#define ll long long
#define pb push_back
#define eps 0.00001
#define DIFF 10000
#define PRECIZ 10000

int n,sol;
vector< pi > myhash[MOD + 5];
pi v[NMAX];
char s[1006];

inline void baga_in_hash(pi a)
{
    int val1 = a.x + DIFF * PRECIZ,val2 = a.y + DIFF * PRECIZ;
    int key = (ll)val1 * val2 % MOD;
    myhash[key].pb(mp(val1,val2));
}

inline int find_hash(pi a)
{
    int val1 = a.x + DIFF * PRECIZ,val2 = a.y + DIFF * PRECIZ;
    int key = (ll)val1 * val2 % MOD;
    int i,lim = myhash[key].size();
    pi p;

    for(i = 0; i < lim; i++)
    {
        p = myhash[key][i];
        if(p == mp(val1,val2))
            return 1;
    }
    return 0;
}

int main ()
{
    int i,j,dx,dy,semn;
    pi p1,p2;

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

    scanf("%d\n",&n);
    for(i = 1; i <= n; i++)
    {
        scanf("%s",s);
        int lim = strlen(s);
        int nr = 0;
        if(s[0] == '-')
        {
            semn = -1;
            nr = 1;
        }
        else
            semn = 1;
        while(nr < lim)
        {
            if(s[nr] != '.')
                v[i].x = v[i].x * 10 + s[nr] - '0';
            nr++;
        }
        v[i].x *= semn;
        scanf("%s",s);
         nr = 0;
        if(s[0] == '-')
        {
            semn = -1;
            nr = 1;
        }
        else
            semn = 1;
        lim = strlen(s);
        while(nr < lim)
        {
            if(s[nr] != '.')
                v[i].y = v[i].y * 10 + s[nr] - '0';
            nr++;
        }
        v[i].y *= semn;
        baga_in_hash(v[i]);
    }
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(i != j && v[i].x < v[j].x && v[i].y - eps < v[j].y)
            {
                dx = v[j].x - v[i].x;
                dy = v[j].y - v[i].y;
                p1.x = v[i].x + dy;
                p1.y = v[i].y - dx;
                p2.x = v[j].x + dy;
                p2.y = v[j].y - dx;
                if(find_hash(p1) && find_hash(p2))
                    sol++;
            }
    printf("%d\n",sol);
    return 0;
}