Cod sursa(job #2648235)

Utilizator Y.MalmsteenB.P.M. Y.Malmsteen Data 9 septembrie 2020 16:16:21
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;
const double EPS = 1e-5;

struct Punct
{
    double x, y;
};

int N;
Punct P[1501];

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

double dist2(const Punct &A, const Punct &B)
{
    double dx = A.x - B.x,
           dy = A.y - B.y;
    return dx * dx + dy * dy;
}

int egal(double a, double b)
{
    double d = a - b;
    if(d < -EPS)return -1;
    if(d > +EPS)return +1;
    return 0;
}

int egal(const Punct &A, const Punct &B)
{
    int ex = egal(A.x, B.x),
        ey = egal(A.y, B.y);
    if(ex == 0) return ey;
    return ex;
}

bool comp(const Punct &A, const Punct &B)
{
    return egal(A, B) < 0;
}

bool cautbin(const Punct &A)
{
    int p = 1, u = N;
    while(p <= u)
    {
        int m = (p + u) / 2;
        int e = egal(P[m], A);
        if(e == 0)
            return 1;
        if(e == 1)
            u = m - 1;
        else
            p = m + 1;
    }
    return 0;
}


int main()
{
    int i, j, nrTr = 0;
    f >> N;
    for(i = 1; i <= N; i++)
        f >> P[i].x >> P[i].y;
    //
    sort(P + 1, P + N + 1, comp);
    //
    double dd2, tga, ddx, ddy;
    Punct M, C, D;
    for(i = 1; i < N; i++)
        for(j = i + 1; j <= N; j++)
        {
            M.x = (P[i].x + P[j].x) / 2;
            M.y = (P[i].y + P[j].y) / 2;
            dd2 = dist2(P[i], P[j]);
            if(egal(P[i].x, P[j].x) == 0)
            {
                ddx = sqrt(3 * dd2) / 2;
                C.x = M.x + ddx;
                D.x = M.x - ddx;
                C.y = M.y;
                D.y = M.y;
            }
            else
            {
                tga = (P[j].y - P[i].y) / (P[j].x - P[i].x);
                ddy = sqrt(3 * dd2 / (1 + tga * tga)) / 2;
                ddx = tga * ddy;
                C.x = M.x + ddx;
                D.x = M.x - ddx;
                C.y = M.y - ddy;
                D.y = M.y + ddy;
            }
            nrTr += cautbin(C);
            nrTr += cautbin(D);
        }
    g << nrTr / 3 << '\n';
    return 0;
}