Cod sursa(job #2277765)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 6 noiembrie 2018 20:17:46
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <bits/stdc++.h>

using namespace std;

struct point
{
    double x, y;
} a[2009];

int n, nr;

int cmp(point A, point B)
{
    return A.x<B.x || (A.x==B.x && A.y<B.y) ;
}

bool bs(double x, double y)
{
    int st=0, dr=n-1;
    int m;
    double dx, dy;
    while (st<=dr)
    {
        m = (st+dr)/2;
        dx = a[m].x - x;
        dy = a[m].y - y;
        if (abs(dx) < (double)0.0001)   // x e fixat
        {
            if (abs(dy) < (double)0.0001)
                return true;
            if (dy>(double)0.0001)
            {
                dr = m-1;
            }
            if (-dy>(double)0.0001)
            {
                st = m+1;
            }
        }
        if (dx > (double)0.0001)
        {
            dr = m-1;
        }
        if (-dx > (double)0.0001)
        {
            st = m+1;
        }
    }
    return false;
}

int main()
{
    ifstream fin ("triang.in");
    ofstream fout ("triang.out");
    fin>>n;
    for (int i=0; i<n; ++i)
    {
        fin>>a[i].x>>a[i].y;
    }
    sort(a, a+n, cmp);
    double a,b,c, alpha, cp, xp, yp, kns = sqrt(3)/2, l;
    double pp;
    point m;
    for (int i=0; i<n-1; ++i)
    {
        for (int j=i+1; j<n; ++j)
        {
            if ((i-j))
            {
                m.x = (a[i].x+a[j].x)/2;
                m.y= (a[i].y+a[j].y)/2;
                a = a[j].y-a[i].y;
                b = a[i].x-a[j].x;
                c = a[i].y*a[j].x-a[i].x*a[j].y;
                pp = (a*a)+(b*b);
                l = sqrt(pp);
                alpha = pp*kns;
                cp = a*m.y-b*m.x;

                xp = (a*alpha-cp*b-a*c)/(pp);
                if (b)
                {
                    yp = (alpha-c-a*xp)/b;
                }
                else
                {
                    yp = cp / a;
                }
                // search
                if (bs(xp, yp))
                {
                    nr ++;
                }

                alpha*=-1;
                xp = (a*alpha-cp*b-a*c)/(pp);
                if (b)
                {
                    yp = (alpha-c-a*xp)/b;
                }
                else
                {
                    yp = cp / a;
                }
                if (bs(xp, yp))
                {
                    nr ++;
                }
            }
        }
    }
    fout<<nr/3;
}