Cod sursa(job #2021119)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 12 septembrie 2017 18:34:26
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

const int N = 1505;
const double EPS = 1e-3;
int ind[N], n, i, j, sol;
double x[N], y[N], px, py, ung, lg;

bool cmp(int a, int b) {
    return x[a] == x[b] ? y[a] < y[b] : x[a] < x[b];
}

bool cb(double X, double Y) {
    int st = 1, dr = n, mij;


    while (st <= dr) {
        mij = (st+dr)/2;
        if (abs(X-x[ind[mij]]) < EPS && abs(Y-y[ind[mij]]) < EPS)
            return 1;

        if ( x[ind[mij]]-X > EPS ||
            (abs( x[ind[mij]]-X ) < EPS && y[ind[mij]]-Y > EPS ))
            dr = mij-1;
        else st = mij+1;
    }
    return 0;
}

int main() {
    f >> n;
    for (i = 1; i <= n; i++) {
        f >> x[i] >> y[i];
        ind[i] = i;
    }
    sort(ind+1, ind+n+1, cmp);

    for (i = 1; i <= n; i++)
        for (j = i+1; j <= n; j++) {
            ung = atan2( (y[ind[j]] - y[ind[i]]), (x[ind[j]]-x[ind[i]]) );
            lg = sqrt( (y[ind[j]] - y[ind[i]])*(y[ind[j]] - y[ind[i]]) + (x[ind[j]]-x[ind[i]])*(x[ind[j]]-x[ind[i]]) );

            px = x[ind[i]] + lg*cos(ung-M_PI/3);
            py = y[ind[i]] + lg*sin(ung-M_PI/3);

            if (cb(px, py))
                sol++;

            px = x[ind[i]] + lg*cos(ung+M_PI/3);
            py = y[ind[i]] + lg*sin(ung+M_PI/3);

            if (cb(px, py))
                sol++;

        }
    g << sol/3;
}