Cod sursa(job #2327545)

Utilizator MAXIMILLIANMUSOHYEAHYEAH MAXIMILLIANMUS Data 24 ianuarie 2019 19:23:59
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
	
#include <bits/stdc++.h>
 
#define Nmax 20000
 
using namespace std;
 
struct point
{
    double x, y;
} arr[Nmax];
 
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 = arr[m].x - x;
        dy = arr[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>>arr[i].x>>arr[i].y;
    }
    sort(arr, arr+n, cmp);
    double a,b,c, alpha, cp, xp, yp, kns = sqrt(3)/2, l;
    double pp;
    point m;
    int i,j;
    for (i=0; i<n-1; ++i)
    {
        for (j=i+1; j<n; ++j)
        {
            if ((i-j))
            {
                m.x=(arr[i].x+arr[j].x)/2;
                m.y=(arr[i].y+arr[j].y)/2;
                a=arr[j].y-arr[i].y;
                b=arr[i].x-arr[j].x;
                c=arr[i].y*arr[j].x-arr[i].x*arr[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;
}