Cod sursa(job #1067957)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 27 decembrie 2013 18:24:27
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.97 kb
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std ;
const int Nmax = 1005;
const int Mod = 1000007;
const int a = 3;
struct Point
{
    int x, y;
};
struct Hash
{
    vector < Point > V[Mod];
    inline void Insert(const Point A)
    {
        int codif = (1LL*A.x*a + 1LL*(A.y & (-A.y)))%Mod;
        codif = abs(codif)%Mod;
        V[codif].push_back(A);
    }
    inline bool Find(const Point A)
    {
        int codif = (1LL*A.x*a + 1LL*(A.y & (-A.y)))%Mod;
        codif = abs(codif)%Mod;
        for(vector < Point  > :: iterator it = V[codif].begin(); it != V[codif].end(); ++it)
            if((*it).x == A.x && (*it).y == A.y )
                return true;
        return false;
                
    }
};
inline void ToNumber(const string S,int &X)
{
    int i,sign = 1;
    for(i = 0,X = 0;S[i]; ++i) 
    {
        if('0' <= S[i] && S[i]<='9')
            X = X * 10 + S[i]-'0';
        else
            if(S[i]=='-')
                 sign = -1;
     }
     X *= sign;
}
Hash H;
int n, sol;
Point A[Nmax];
inline void Read()
{
    ifstream f("patrate3.in");
    f >> n;
    string S;
    for(int i = 1;i <= n; ++i)
    {
        f>> S;
        ToNumber(S,A[i].x);
        f >> S;
        ToNumber(S,A[i].y);
        A[i].x *= 2;A[i].y *= 2;
        H.Insert(A[i]);
    }
    f.close();
}

inline void Solve()
{
    int i, j, mx, my;
    Point B,C,D;
    for(i = 1;i <= n; ++i)
        for(j = 1;j <= n; ++j)
            if(i != j && A[i].x <= A[j].x  && A[i].y < A[j].y)
            {
                D.x = (A[i].x + A[j].x)/2;  D.y = (A[i].y + A[j].y)/2;
                mx = abs(D.x - A[i].x);  my = (D.y - A[i].y);
                B.x = D.x + my; B.y = D.y - mx;
                C.x = D.x - my; C.y = D.y + mx;
                if(H.Find(B) && H.Find(C) )
                    ++sol;
            }
}

inline void Write()
{
    ofstream g("patrate3.out");
    g<<sol<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}