Cod sursa(job #1792018)

Utilizator Y0da1NUME JMECHER Y0da1 Data 29 octombrie 2016 22:42:24
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>

using namespace std;

# define ERR 0.001

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

int N;

struct punct{
    double x;
    double y;
};

punct puncte[2000];
int cmp(punct p1, punct p2)
{
    //sortez dupa abscisa (adica x, sau care o fi)
    if(p1.x<p2.x)
        return 1;
    else
        if(p1.x>p2.x)
            return 0;
    if(p1.y<p2.y) //daca au abscisele egale sortam dupa y
        return 1;
    return 0;
}
int cautbin(double  x, double y)
{
    int st=1, dr=N, mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if((puncte[mij].x-x <= ERR) && (puncte[mij].x-x >= -ERR) && (puncte[mij].y-y <= ERR) && (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, i;
    double xm, ym, x1, y1, x2, y2, dist, panta;
    in>>N;
    for(i=1;i<=N;++i)
    {
        in>>puncte[i].x>>puncte[i].y;
    }
    sort(puncte+1,puncte+N+1,cmp);
    for(i=1;i<=N;++i)
        for(int j = i + 1;j<=N;++j)
        {
            xm = (puncte[i].x + puncte[j].x) /2;
            ym = (puncte[i].y + puncte[j].y) /2;
            x1=0;y1=0;x2=0;y2=0;
            dist = (puncte[j].x - puncte[i].x)*(puncte[j].x - puncte[i].x) + (puncte[j].y - puncte[i].y)*(puncte[j].y - puncte[i].y);
            panta = 0;

            if(fabs(puncte[j].y - puncte [i].y) <ERR)
            {
                x1=x2=xm;
                y1=ym + sqrt(3.0)*sqrt(dist) / 2;
                y2=ym - sqrt(3.0)*sqrt(dist) / 2;
            }
            else
            {
                if (fabs(puncte[j].x - puncte[i].x)<ERR)
                {
                    panta = 0;
                }
                else
                {
                    panta = - (puncte[j].x - puncte[i].x)/(puncte[j].y - puncte[i].y);
                }
                x1 = (2 * xm + sqrt(3 * dist / (panta*panta + 1))) / 2;
                x2 = (2 * xm - sqrt(3 * dist / (panta*panta + 1))) / 2;

                y1 = x1*panta - panta*xm + ym;
                y2 = x2*panta - panta*xm + ym;

            }
            punct ptemp;
            ptemp.x=x1;
            ptemp.y=y1;
            nr+=cautbin(x1, y1);
            ptemp.x=x2;
            ptemp.y=y2;
            nr+=cautbin(x2, y2);
        }
        out<<nr/3;
    return 0;
}