Cod sursa(job #1789931)

Utilizator Y0da1NUME JMECHER Y0da1 Data 27 octombrie 2016 17:20:11
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
//#include <iostream>
#include <fstream>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;

# define ERR 0.001

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

struct punct{
    double x;
    double y;
};

vector <punct> H[600010];
punct puncte[2000];
int rotunjeste(double x)
{
    int a;
    a=x*1000;
    if(abs( ( (int)(x*10000) ) %10) >5 )
    {
        if(x<0)
            --a;
        else
            ++a;
    }
    return a;
}
long long get_key(punct p)
{

    int a = rotunjeste(p.x);
    int b = rotunjeste(p.y);
    int var = (a * 2 + b * 3) % 600003;
    if (var < 0)
        var += 600003;
    return var;
}
void insertq(punct p)
{
    H[get_key(p)].push_back(p);
}
bool cautaInHash(punct p)
{
    long long key = get_key(p);
    for (int i=0;i<H[key].size();++i)
        if(fabs(p.x - H[key][i].x) < ERR && fabs(p.y - H[key][i].x) < ERR)    //am gasit in tabela hash
        return true;
    return false;
}
int main()
{
    int N, nr = 0, i;
    double xm, ym, x1, y1, x2, y2, dist, panta;
    in>>N;
    for(i=1;i<=N;++i)
    {
        in>>puncte[i].x>>puncte[i].y;
        insertq(puncte[i]);
    }
    for(i=1;i<=N;++i)
        for(int j = i + 1;j<=N;++j)
        {
            xm = (puncte[i].x + puncte[j].y) /2;
            ym = (puncte[i].y + puncte[j].y) /2;
            x1=0;y1=0;x2=0;y2=0;
            dist = (puncte[j].x - puncte[i].x)*(puncte[j].x - puncte[i].x) + (puncte[j].y - puncte[i].y)*(puncte[j].y - puncte[i].y);
            panta = 0;

            if(fabs(puncte[j].y - puncte [i].y) <ERR)
            {
                x1=x2=xm;
                y1=ym + sqrt(3.0)*sqrt(dist) / 2;
                y2=ym - sqrt(3.0)*sqrt(dist) / 2;
            }
            else
            {
                if (fabs(puncte[j].x - puncte[i].x)<ERR)
                {
                    panta = 0;
                }
                else
                {
                    panta = - (puncte[j].x - puncte[i].x)/(puncte[j].y - puncte[i].y);
                }
                x1 = (2 * xm + sqrt(3 * dist / (panta*panta + 1))) / 2;
                x2 = (2 * xm - sqrt(3 * dist / (panta*panta + 1))) / 2;

                y1 = x1*panta - panta*xm + ym;
                y2 = x2*panta - panta*xm + ym;

            }
            punct ptemp;
            ptemp.x=x1;
            ptemp.y=y1;
            if(cautaInHash(ptemp) == 1)
                ++nr;
            ptemp.x=x2;
            ptemp.y=y2;
            if(cautaInHash(ptemp) == 1)
                ++ nr;
        }

}
/*

}*/