Cod sursa(job #1777609)

Utilizator andru47Stefanescu Andru andru47 Data 12 octombrie 2016 18:19:15
Problema Patrate 3 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <bits/stdc++.h>
#define per pair<int,int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define MOD 666013
using namespace std;
const int NMAX = 1000 + 5;

int n,sol=0;
double x,y;
per v[NMAX];
vector <pair<long long,pair<int,int> > > Hash[MOD];

inline void add_hash(int p1, int p2)
{
    int x1 = v[p1].f , y1 = v[p1].s, x2 = v[p2].f , y2 = v[p2].s;
    long long dist = 1LL*(x2-x1)*(x2-x1) + 1LL*(y2-y1)*(y2-y1);
    int mask = dist% MOD;
    Hash[mask].pb(mp(dist,mp(p1,p2)));
    return ;
}

inline void check(int p1, int p2)
{
    int x1 = v[p1].f , y1 = v[p1].s, x2 = v[p2].f , y2 = v[p2].s;
    long long dist = 1LL*(x2-x1)*(x2-x1) + 1LL*(y2-y1)*(y2-y1);
    int mask = dist % MOD;
    for (auto &it : Hash[mask])
    {
        if (dist==it.f&&p1!=it.s.f&&p1!=it.s.s&&p2!=it.s.f&&p2!=it.s.s)
        {
            per x = v[p1];
            per y = v[p2];
            per X = v[it.s.f];
            per Y = v[it.s.s];
            long long dist1 = 1LL*(X.f-x.f)*(X.f-x.f)+1LL*(X.s-x.s)*(X.s-x.s);
            long long ddist1 = 1LL*(Y.f-y.f)*(Y.f-y.f)+1LL*(Y.s-y.s)*(Y.s-y.s);
            long long dist2 = 1LL*(Y.f-x.f)*(Y.f-x.f)+1LL*(Y.s-x.s)*(Y.s-x.s);
            long long ddist2 = 1LL*(X.f-y.f)*(X.f-y.f)+1LL*(X.s-y.s)*(X.s-y.s);
            if (dist1==ddist1&&dist1==dist)
            {
                ++sol;
                continue;
            }
            if (dist2==ddist2&&dist2==dist)++sol;

        }

    }
    for (auto it = Hash[mask].begin(); it!=Hash[mask].end(); ++it)
    {
        pair<long long,pair<int,int> > ix = *it;
        if (ix.s.f==p1&&ix.s.s==p2)
        {
            Hash[mask].erase(it);
            break;
        }
    }
}
int main()

{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    scanf("%d\n", &n);

    for (int i = 1; i<=n; ++i)
    {
        scanf("%lf %lf\n", &x, &y);
        x = round(x*10000);
        y = round(y*10000);
        int X = x;
        int Y = y;
        v[i].f = X;
        v[i].s = Y;
    }
    for (int i = 1; i<=n; ++i)
        for (int j = i + 1; j<=n; ++j)
            add_hash(i,j);
    for (int i = 1; i<=n; ++i)
        for (int j = i+1; j<=n; ++j)
            check(i,j);
    printf("%d\n", sol/2);
    return 0;
}