Cod sursa(job #1036025)

Utilizator PsychoAlexAlexandru Buicescu PsychoAlex Data 18 noiembrie 2013 22:21:36
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.24 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>

std::ifstream fin("triang.in");
std::ofstream fout("triang.out");

struct punct
{
    double x, y;
};

struct triunghi
{
    punct a, b, c;
};

int n;
punct vec[1501];
punct mostLeft, mostRight;

inline bool cmp(punct a, punct b)
{
    if(a.x < b.x)
    {
        return true;
    }
    return false;
}

void citire()
{
    fin>>n;
    mostLeft.x = 10001;
    mostRight.x = -10001;
    for(int i = 0; i < n; i++)
    {
        fin>>vec[i].x>>vec[i].y;
        if(vec[i].x < mostLeft.x)
        {
            mostLeft.x = vec[i].x;
        }
        else
            if(vec[i].x > mostRight.x)
            {
                mostRight.x = vec[i].x;
            }
    }
}

double getPanta(punct a, punct b)
{
    return (double) (b.y - a.y) / (b.x - a.x);
}

double getDist(punct a, punct b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void getTheMoFoPoint(punct a, punct b, punct puncte[])
{
//    puncte[0].x = (double) ((b.x + a.x) - sqrt(3) * (b.y - a.y)) / 2;
//    puncte[0].y = (double) ((b.y + a.y) + sqrt(3) * (b.x - a.x)) / 2;
//
//    puncte[1].x = (double) ((b.x + a.x) + sqrt(3) * (b.y - a.y)) / 2;
//    puncte[1].y = (double) ((b.y + a.y) - sqrt(3) * (b.x - a.x)) / 2;

    double panta = getPanta(a, b);
    panta = (double) (-1) / panta;
    double var = (double) getDist(a, b) * sqrt(3) / 2;
    punct c;
    c.x = (double) (a.x + b.x) / 2;
    c.y = (double) (a.y + b.y) / 2;

    puncte[0].x = (double) c.x + (var * panta / sqrt(1 + panta * panta));
    puncte[1].x = (double) c.x + (-var * panta / sqrt(1 + panta * panta));

    puncte[0].y = (double) c.y - (var / sqrt(1 + panta * panta));
    puncte[1].y = (double) c.y - (-var / sqrt(1 + panta * panta));

//    std::cout<<(1 / 2) * ((b.x + a.x) - sqrt(3) * (b.y - a.y))<<'\n';
    std::cout<<puncte[0].x<<' '<<puncte[0].y<<"; "<<puncte[1].x<<' '<<puncte[1].y<<'\n';
}

bool binSearch(punct a)
{
    int left = 0, right = n - 1;

    while(left < right)
    {
        int m = left / 2 + right / 2;
        if(vec[m].x < a.x - 0.001)
        {
//            std::cout<<vec[m].x<<' '<<a.x - 0.001<<'\n';
//            std::cout<<"here1"<<'\n';
            left = m + 1;
        }
        else
            if(vec[m].x > a.x + 0.001)
            {
//                std::cout<<"here2"<<'\n';
                right = m - 1;
            }
            else
            {
                if(vec[m].y <= a.y + 0.001 && vec[m].y >= a.y - 0.001)
                {
                    return true;
                }
                return false;
            }
    }
    return false;
}

void rezolvare1()
{
    std::sort(vec, vec+n, cmp);

    int nr = 0;
    for(int i = 0; i < n - 1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            punct pun[2];
            getTheMoFoPoint(vec[i], vec[j], pun);
//            std::cout<<i<<' '<<j<<": "<<pun[0].x<<' '<<pun[0].y<<"; "<<pun[1].x<<' '<<pun[1].y<<'\n';
//            std::cout<<binSearch(pun[0])<<' '<<binSearch(pun[1])<<'\n';
            if(binSearch(pun[0]))
            {
                nr++;
            }
            if(binSearch(pun[1]))
            {
                nr++;
            }
        }
    }
    fout<<nr<<'\n';
//    for(int i = 0; i < n; i++)
//    {
//        std::cout<<vec[i].x<<' '<<vec[i].y<<'\n';
//    }
}

void rezolvare2()
{
    int nr = 0;
    for(int i = 0; i < n - 2; i++)
    {
        for(int j = i + 1; j < n - 1; j++)
        {
            int nr2 = 0;
            double dist = getDist(vec[i], vec[j]);
            for(int k = j + 1; k < n; k++)
            {
                double dist1 = getDist(vec[i], vec[k]);
                double dist2 = getDist(vec[j], vec[k]);

                if(dist - dist1 <= 0.001 && dist - dist2 <= 0.001 && dist1 - dist2 <= 0.001)
                {
                    nr++;
                    nr2++;
                }
                if(nr2 == 2)
                {
                    break;
                }
            }
        }
    }
    fout<<nr<<'\n';
}

int main()
{
    citire();
//    rezolvare1();
    rezolvare2();
    return 0;
}