Cod sursa(job #2363879)

Utilizator Y0da1NUME JMECHER Y0da1 Data 3 martie 2019 18:34:46
Problema Triang Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>

using namespace std;

#define ERR 0.001
#define PI 3.14159265

int N;

struct punct{
    double x;
    double y;
};

punct puncte[2005];

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;
    ifstream in("triang.in");
    ofstream out("triang.out");

    in>>N;
    for(int i = 1; i <= N; ++i)
        in>>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;
            punct p1, p2;
            p1.x = puncte[i].x;
            p1.y = puncte[i].y;

            p2.x = puncte[j].x;
            p2.y = puncte[j].y;
            //cout<<"Analizez punctele ("<<p1.x<<", "<<p1.y<<"), ("<<p2.x<<", "<<p2.y<<")\n";
            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
            dist = 0.5d * sqrt(3 * dist);

            double theta = atan2((p2.y - p1.y), (p2.x - p1.x)); ///caut unghiul dreptei formate din aceste doua puncte cu orizontala
            //cout<<"Dreapta este inclinata la un unghi de "<<theta * 180/PI<<"\n";
            ///trebuie sa generez 2 versori, unul rotit la dreapta cu PI/2 si unul la stanga tot cu PI/2
            double theta1 = theta - PI/2;
            double theta2 = theta + PI/2;

            //cout<<"Theta 1:"<<theta1 * 180/PI<<"\n";
            //cout<<"Theta 2:"<<theta2 * 180/PI<<"\n";
            x1 = dist * cos(theta1) + xm;
            y1 = dist * sin(theta1) + ym;

            x2 = dist * cos(theta2) + xm;
            y2 = dist * sin(theta2) + ym;

            //cout<<"Am generat ("<<x1<<", "<<y1<<"), ("<<x2<<", "<<y2<<")\n";

            nr += cautbin(x1, y1);
            nr += cautbin(x2, y2);
            //cout<<'\n';
        }
    out<<nr/3;
    return 0;
}