Cod sursa(job #1474736)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 22 august 2015 18:51:15
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <cmath>
#include <vector>

#define mod 666013
#define point pair<double,double>
#define x first
#define y second
#define maxn 1510

using namespace std;

ifstream fin("triang.in");
ofstream fout("triang.out");

point v[maxn];
vector<point> H[mod];
int n;

int hashf(point &p)
{
    int h = ((int)p.x*1000*2 + (int)p.y*1000*3)%mod;
    if (h < 0)
        h += mod;
    return h;
}

void insert(point &p)
{
    int h = hashf(p);
    H[h].push_back(p);
}

bool equal(point &a, point &b)
{
    return (fabs(a.x-b.x) < 1e-3 && fabs(a.y-b.y) < 1e-3);
}

int search(point &p)
{
    int h = hashf(p);
    for (int i = 0; i < H[h].size(); ++i)
    {
        if (equal(H[h][i], p))
            return 1;
    }

    return 0;
}

int main()
{
    fin >> n;

    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i].x >> v[i].y;
        insert(v[i]);
    }

    int answer = 0;
    double sq3 = sqrt(3);

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (i == j)
                continue;

            point vec = make_pair((v[i].x - v[j].x)*sq3/2, (v[i].y - v[j].y)*sq3/2);
            point mid = make_pair((v[i].x + v[j].x)/2, (v[i].y + v[j].y)/2);
            point s1 = make_pair(mid.x - vec.y, mid.y + vec.x);
            answer += search(s1);
            point s2 = make_pair(mid.x + vec.y, mid.y - vec.x);
            answer += search(s2);
        }
    }

    fout << answer/3;
}