Cod sursa(job #2250940)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 30 septembrie 2018 21:11:06
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <map>
#include <algorithm>
#define COS 0.5
#define SIN 0.86602540378
#define VAL 1505
#define EPS 0.0001

using namespace std;

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

int N, i, j, ANS;
double X, Y, X1, Y1;
pair <double, double> P[VAL];

double MODUL(double X)
{
    return max(X, -X);
}

int Cautbin(double X, double Y)
{
    int poz=j+1, i, nr;
    for (i=10; i>=0; i--)
    {
        nr=poz+(1 << i);
        if (nr<=N)
        {
            if (MODUL(P[nr].first-X)<=EPS && MODUL(P[nr].second-Y)<=EPS)
                return 1;
            if (P[nr].first<X || (P[nr].first==X && P[nr].second<Y))
                poz=nr;
        }
    }
    if (MODUL(P[poz].first-X)<=EPS && MODUL(P[poz].second-Y)<=EPS)
        return 1;
    return 0;
}

int main()
{
    fin >> N;
    for (i=1; i<=N; i++)
        fin >> P[i].first >> P[i].second;
    sort(P+1, P+N+1);
    for (i=1; i<=N-2; i++)
    {
        for (j=i+1; j<=N-1; j++)
        {
            X=(P[i].first+P[j].first) / 2;
            Y=(P[i].second+P[j].second) / 2;
            X1=X+(SIN*(P[j].second-P[i].second));
            Y1=Y+(SIN*(P[i].first-P[j].first));
            ANS+=Cautbin(X1, Y1);
            X1=X+(SIN*(P[i].second-P[j].second));
            Y1=Y+(SIN*(P[j].first-P[i].first));
            ANS+=Cautbin(X1, Y1);
        }
    }
    fout << ANS << '\n';
    fin.close();
    fout.close();
    return 0;
}