Cod sursa(job #3159693)

Utilizator AswVwsACamburu Luca AswVwsA Data 21 octombrie 2023 20:00:24
Problema Triang Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
//oftica si durere in suflet
#include <fstream>
#include <cmath>
#include <algorithm>
#define ll long long

using std :: pair, std :: swap, std :: sort;

const int NMAX = 1500;
const double EPS = 0.01;

struct pct
{
    double x, y;
};

double equal(double a, double b)
{
    return abs(a - b) < EPS;
}

double less(double a, double b)
{
    return b - a > EPS;
}

double greater(double a, double b)
{
    return less(b, a);
}


bool operator <(pct a, pct b)
{
    if (a.x != b.x)
        return less(a.x, b.x);
    return less(a.y, b.y);
}

bool operator >(pct a, pct b)
{
    return b < a;
}

pct v[NMAX + 1];

pair <pct, pct> calculate(pct a, pct b)
{
    //pentru 2 puncte date, calculati al 3-lea punct a.i.
    //triunghiul format de ele sa fie echilateral
    bool ok = 0;
    if (a.x == b.x)
    {
        ok = 1;
        swap(a.x, a.y);
        swap(b.x, b.y);
    }

    if (a.y == b.y)
    {
        double x = (a.x + b.x) / 2.0;
        double B = 2.0 * a.y;
        double C = a.y * a.y - 3.0 * (b.x - a.x) * (b.x - a.x) / 4.0;
        double delta = sqrt(B * B - 4.0 * C);
        double y1 = (-B + delta) / 2.0;
        double y2 = (-B - delta) / 2.0;


        if (ok)
            return {{y1, x}, {y2, x}};
        else
            return {{x, y1}, {x, y2}};
    }

    double m = (a.x - b.x) / (b.y - a.y);
    double n = (b.y * b.y - a.y * a.y + b.x * b.x - a.x * a.x) / (2.0 * (b.y - a.y));
    double A = m * m + 1.0;
    double B = 2.0 * (m * n - a.x - m * a.y);
    double C = -2.0 * n * a.y - b.y * b.y - b.x * b.x + 2 * a.y * b.y + 2.0 * a.x * b.x + n * n;

    double delta = sqrt(B * B - 4.0 * A * C);

    double x1 = (-B + delta) / (2.0 * A);
    double y1 = m * x1 + n;

    double x2 = (-B - delta) / (2.0 * A);
    double y2 = m * x2 + n;

    return {{x1, y1}, {x2, y2}};
}

int n;

bool gaseste(pct a)
{
    int med, st = 1, dr = n;
    while (st <= dr)
    {
        med = ((st + dr) >> 1);
        if (v[med] < a)
            st = med + 1;
        else if (v[med] > a)
            dr = med - 1;
        else
            return true;
    }
    return false;
}

signed main()
{
    std :: ifstream cin("triang.in");
    std :: ofstream cout("triang.out");
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1);
    int ans = 0;
    for (i = 1; i <= n; i++)
        for (j = i + 1; j <= n; j++)
        {
            pair <pct, pct> sols = calculate(v[i], v[j]);
            ans += gaseste(sols.first);
            ans += gaseste(sols.second);
        }
    cout << ans / 3;
}