Cod sursa(job #2021090)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 12 septembrie 2017 17:42:36
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int N = 1505;
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];
}

double triaza(double &X) {
    X *= 1e3, X = (int)X, X /= 1e3;
}

bool cb(double X, double Y) {
    int st = 1, dr = n, mij;
    while (st <= dr) {
        mij = (st+dr)/2;
        if ( (int)(X*1e3) < (int) (x[ind[mij]]*1e3) ||
            ((int)(X*1e3) == (int) (x[ind[mij]]*1e3) && (int)(Y*1e3) < (int) (y[ind[mij]]*1e3)) )
            dr = mij-1;
        else st = mij+1;
    }


    if ((int)(X*1e3) == (int) (x[ind[mij]]*1e3) && (int)(Y*1e3) == (int) (y[ind[mij]]*1e3))
        return 1;
    return 0;
}

int main() {
    f >> n;
    for (i = 1; i <= n; i++) {
        f >> x[i] >> y[i];

        //triaza(x[i]);
        //triaza(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);


            //triaza(px);
            //triaza(py);
            //cout << px << ' ' << py << '\n';
            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);


            //triaza(px);
            //triaza(py);
            //cout << px << ' ' << py << '\n'; cout << '\n';
            if (cb(px, py))
                sol++;

        }
    g << sol;
}