Cod sursa(job #1166934)

Utilizator andreiiiiPopa Andrei andreiiii Data 3 aprilie 2014 23:31:44
Problema Patrate 3 Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <algorithm>
#include <cstdio>
#include <vector>
#define ll long long

using namespace std;

const int N=1005, MOD=666013;

ll modul(ll k) {return (k<0?-k:k);}

struct pc{
    ll x, y;
    bool operator==(const pc &e) const
    {
        return (x==e.x&&y==e.y);
    }
    pc(){}
    pc(const ll _x, const ll _y)
    {
        x=_x;
        y=_y;
    }
};

class Hash{
public:
    Hash(){}
    bool find(const pc a)
    {
        int p=modul((10LL*a.x+a.y)%MOD);
        for(vector<pc>::iterator it=H[p].begin();it!=H[p].end();it++) if(*it==a) return true;
        return false;
    }
    void insert(const pc a)
    {
        if(find(a)) return;
        int p=modul((10LL*a.x+a.y)%MOD);
        H[p].push_back(a);
    }
private:
    vector<pc> H[MOD];
};

pc a[N];
Hash H;

int main()
{
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
    int n, i, j, x, y, sol=0;
    pc mij, x1, y1;
    scanf("%d\n", &n);
    for(i=1;i<=n;i++)
    {
        scanf("%d.%d ", &x, &y);
        if(x>=0) a[i].x=x*100000LL+y*10;
        else a[i].x=x*100000LL-y*10;
        scanf("%d.%d\n", &x, &y);
        if(x>=0) a[i].y=x*100000LL+y*10;
        else a[i].y=x*100000LL+y*10;
        H.insert(a[i]);
    }
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            mij=pc((a[i].x+a[j].x)/2, (a[i].y+a[j].y)/2);
            x1=pc(mij.x-(a[i].y-mij.y), mij.y+(a[i].x-mij.x));
            y1=pc(mij.x-(a[j].y-mij.y), mij.y+(a[j].x-mij.x));
            if(H.find(x1)&&H.find(y1)) sol++;
        }
    }
    printf("%d\n", sol/2);
}