Cod sursa(job #2552045)

Utilizator DinuD11Dinu Dragomirescu DinuD11 Data 20 februarie 2020 15:24:49
Problema Triang Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>

using namespace std;

int n, nr;

const double ERR = 0.001;
const double PI = 3.14159265;

struct punct {
    double x, y;
} puncte[2000];

int cmp(punct p1, punct p2) {
    if(p1.x == p2.x)
        return p1.y<p2.y;
    return p1.x<p2.x;
}

int cautare_binara(double x, double y) {
    int st = 1, dr = n, mij;
    do {
        mij = (st+dr)/2;
        if(abs(puncte[mij].x - x) <= ERR && abs(puncte[mij].y - y) <= ERR)
            return 1;
        if(puncte[mij].x < x)
            st = mij+1;
        else
            dr = mij-1;
    } while(st <= dr);
    return 0;
}

int main() {
    ifstream fin("triang.in");
    ofstream fout("triang.out");
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> puncte[i].x >> puncte[i].y;
    fin.close();

    sort(puncte + 1, puncte + n+1, cmp);

    double x1, x2, y1, y2, xm, ym, d;
    double alfa, a1, a2;

    for(int i = 1; i <= n; i++) 
        for(int j = i+1; j <= n; j++) {
            x1 = puncte[i].x;
            y1 = puncte[i].y;
            x2 = puncte[j].x;
            y2 = puncte[j].y;

            xm = (x1+x2)/2;
            ym = (y1+y2)/2;

            d = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
            d = 0.5*sqrt(3 * d);

            alfa = atan2((y2-y1), (x2-x1));
            a1 = alfa + PI/2;
            a2 = alfa - PI/2;

            x1 = d * cos(a1) + xm;
            y1 = d * sin(a1) + ym;

            x2 = d * cos(a2) + xm;
            y2 = d * sin(a2) + ym;

            nr += cautare_binara(x1, y1);
            nr += cautare_binara(x2, y2);
        }
    fout << nr/3;
    fout.close();
    return 0;
}