Cod sursa(job #3223248)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 12 aprilie 2024 19:50:00
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <fstream>
#include <set>
#include <cassert>
#include <stack>
#include <algorithm>
#include <cmath>
#define ll long long

using namespace std;

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

const int NMAX = 1500;
const double EPS = 1e-3;
const double SQRT3 = 1.7320508075688772935274463415059;

struct Point
{
    double x, y;
    void Read()
    {
        cin >> x >> y;
    }
};

struct Line
{
    double a, b, c;
};

int n, answer;
Point points[NMAX + 1];

bool cmpP(const Point& p1, const Point& p2)
{
    /// p1.x < p2.x
    /// p1.x < p2.x - EPS

    if (p1.x < p2.x - EPS)
        return true;
    if (abs(p1.x - p2.x) < EPS && p1.y < p2.y - EPS)
        return true;
    return false;
}

bool cmpP2(const Point& p1, const Point& p2)
{
    if (p1.x < p2.x - EPS)
        return true;
    if (abs(p1.x - p2.x) < EPS && p1.y < p2.y - EPS)
        return true;
    if (abs(p1.x - p2.x) < EPS && abs(p1.y - p2.y) < EPS)
        return true;
    return false;
}

bool BS(Point p)
{
    int left = 1, right = n, pos = 0;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (cmpP2(points[mid], p))
            pos = mid, left = mid + 1;
        else
            right = mid - 1;
    }

    if (abs(points[pos].x - p.x) < EPS && abs(points[pos].y - p.y) < EPS)
        return true;
    return false;
}

double Square(double x)
{
    return x * x;
}

double Distance(Point p1, Point p2)
{
    return (Square(p1.x - p2.x) + Square(p1.y - p2.y));
}

pair<double, double> SolveEQ2(double a, double b, double c)
{
    double delta = Square(b) - 4 * a * c;

    pair<double, double> answer;
    answer.first = (-b + sqrt(delta)) / (2 * a);
    answer.second = (-b - sqrt(delta)) / (2 * a);
    return answer;
}

void Solve(Point p1, Point p2)
{
    Point mid = { (p1.x + p2.x) / 2, (p1.y + p2.y) / 2 };

    Line mediator_line;
    mediator_line.a = p2.x - p1.x;
    mediator_line.b = p2.y - p1.y;
    mediator_line.c = -mid.y * (p2.y - p1.y) - mid.x * (p2.x - p1.x);

    double A = -mediator_line.b / mediator_line.a;
    double B = -mediator_line.c / mediator_line.a;
    double V = 3 * Distance(p1, p2) / 4;

    double a = Square(A) + 1;
    double b = 2 * A * B - 2 * mid.x * A - 2 * mid.y;
    double c = Square(B) - 2 * mid.x * B + Square(mid.x) + Square(mid.y) - V;

    pair<double, double> y = SolveEQ2(a, b, c);
    pair<double, double> x;
    x.first = y.first * A + B;
    x.second = y.second * A + B;

    if (BS({ x.first, y.first }))
        answer++;
    if (BS({ x.second, y.second }))
        answer++;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        points[i].Read();

    sort(points + 1, points + n + 1, cmpP);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            Solve(points[i], points[j]);

    cout << answer / 3;

    return 0;
}