Cod sursa(job #3222894)

Utilizator unomMirel Costel unom Data 11 aprilie 2024 20:23:45
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream in("triang.in");
ofstream out("triang.out");
int n, ans;
pair<long double, long double> v[1505];
long double DIF = 0.001;

bool cmp(const pair<long double, long double> &a, const pair<long double, long double> &b)
{
    if(fabs(a.first - b.first) < DIF)
    {
        return a.second < b.second;
    }
    else
    {
        return a.first < b.first;
    }
}

int cb(long double x, long double y)
{
    int st = 1;
    int dr = n;
    int mij;

    while(st <= dr)
    {
        mij = (st + dr) / 2;

        if(fabs(v[mij].first - x) < DIF && fabs(v[mij].second - y) < DIF)
        {
            return 1;
        }
        else if((fabs(v[mij].first - x) < DIF && v[mij].second < y) || v[mij].first < x)
        {
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }

    return 0;
}

int main()
{
    in>>n;

    for(int i = 1; i<=n; i++)
    {
        in>>v[i].first>>v[i].second;
    }

    sort(v+1, v+n+1, cmp);

    long double dx, dy, x, y;
    for(int i = 1; i<=n; i++)
    {
        for(int j = i + 1; j<=n; j++)
        {
            dx = v[j].first - v[i].first;
            dy = v[j].second - v[i].second;

            x = v[i].first + dx / 2 - (sqrt(3) / 2) * dy;
            y = v[i].second + dy / 2 + (sqrt(3) / 2) * dx;
            if(cb(x, y))
            {
                ans++;
            }

            x = v[i].first + dx / 2 + (sqrt(3) / 2) * dy;
            y = v[i].second + dy / 2 - (sqrt(3) / 2) * dx;
            if(cb(x, y))
            {
                ans++;
            }
        }
    }

    out<<ans / 3;

    return 0;
}