Cod sursa(job #2646271)

Utilizator AndreiAlexandru2k3Ciucan Andrei Alexandru AndreiAlexandru2k3 Data 31 august 2020 16:20:18
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <algorithm>
#include <math.h>

using namespace std;

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

const double ERR = 0.001;
const double PI = 3.14159265;

int N;

struct punct
{
    double x;
    double y;
};

punct puncte[2005];

int cmp(const punct &p1,const punct &p2)
{
    if(p1.x == p2.x)
        return p1.y < p2.y;
    return p1.x < p2.x;
}

int cautbin(double  x, double y)
{
    int st = 1, dr = N, mij;
    while(st <= dr)
    {
        mij = (st + dr)/2;
        if(abs(puncte[mij].x - x) <= ERR && abs(puncte[mij].y - y) <= ERR)
            return 1;
        else
        {
            if(puncte[mij].x < x)
                st = mij + 1;
            else
                dr = mij - 1;
        }
    }
    return 0;
}

int main()
{
    int nr = 0;
    f>>N;
    for(int i = 1; i <= N; ++i)
        f>>puncte[i].x>>puncte[i].y;
    sort(puncte + 1, puncte + N + 1, cmp);
    for(int i = 1; i <= N; ++i)
        for(int j = i + 1; j <= N; ++j)
        {
            double xm, ym, x1, y1, x2, y2, dist, panta;
            punct p1, p2;
            p1.x = puncte[i].x;
            p1.y = puncte[i].y;
            p2.x = puncte[j].x;
            p2.y = puncte[j].y;
            xm = (p1.x + p2.x) / 2;
            ym = (p1.y + p2.y) / 2;
            dist = (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);   ///nu calculez distanta cu sqrt deoarece mai fac operatii pe ea si as pierde precizia
            double dist2 = dist;
            if(abs(p2.x - p1.x) < ERR)
            {
                y1 = ym;
                y2 = ym;

                x1 = xm + 0.5d * sqrt(3 * dist);
                x2 = xm - 0.5d * sqrt(3 * dist);
            }
            else
            {
                panta = (p2.y - p1.y)/(p2.x - p1.x);
                x1 = 0.5d * panta * sqrt(3 * dist2 / (1 + panta * panta)) + xm;
                y1 = -0.5d * sqrt(3 * dist2 / (1 + panta * panta)) + ym;

                x2 = -0.5d * panta * sqrt(3 * dist2 / (1 + panta * panta)) + xm;
                y2 = 0.5d * sqrt (3 * dist2 / (1 + panta * panta)) + ym;
            }
            nr += cautbin(x1, y1);
            nr += cautbin(x2, y2);
        }
    g<<nr/3;
    return 0;
}