Cod sursa(job #1167011)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 4 aprilie 2014 10:35:29
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include<stdio.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;
  //  printf("In cheie %d am bagat %d %d\n",key,val1,val2);
    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;
//printf("vreau sa gasesc %d %d si sunt in %d cu %d %d\n",a.x,a.y,key,val1,val2);
    int i,lim = myhash[key].size();
    pi p;

    for(i = 0; i < lim; i++)
    {
        //printf("vreau sa gasesc %.4lf %.4lf\n",a.x,a.y);
        p = myhash[key][i];
        if(p == mp(val1,val2))
            return 1;
    }
    return 0;
}

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

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

    scanf("%d\n",&n);
    for(i = 1; i <= n; i++)
    {
        /*scanf("%lf%lf",&a,&b);
        v[i] = mp(a * PRECIZ,b * (double)PRECIZ);
         printf("%.4lf %.4lf %d %d\n",a,b,v[i].x,v[i].y);*/
        scanf("%s",s);
        int lim = strlen(s);
        int nr = 0;
        while(nr < lim)
        {
            if(s[nr] != '.')
                v[i].x = v[i].x * 10 + s[nr] - '0';
          //  printf("%d %d\n",v[i].x,v[i].y);
            nr++;
         //   printf("Si acum s[%d] = %c\n",nr,s[nr]);
        }
        scanf("%s",s);
        lim = strlen(s);
        nr = 0;
        while(nr < lim)
        {
            if(s[nr] != '.')
                v[i].y = v[i].y * 10 + s[nr] - '0';
            //printf("%d %d\n",v[i].x,v[i].y);
            nr++;
            //printf("Si acum s[%d] = %c\n",nr,s[nr]);
        }
        //printf("%d %d\n",v[i].x,v[i].y);
        baga_in_hash(v[i]);
    }
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            //       printf("%d %d\n",i,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;
              //  if(i == 6 && j == 1)
                //    printf("%d %d %d\n",v[i].x, 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(i == 6 && j == 1)
                  //  printf("%.4lf %.4lf %.4lf %.4lf\n",p1.x,p1.y,p2.x,p2.y);
                if(find_hash(p1) && find_hash(p2))
                    sol++;
            }
        }
    printf("%d\n",sol);
    return 0;
}