Cod sursa(job #1112822)

Utilizator Theorytheo .c Theory Data 20 februarie 2014 02:10:50
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <algorithm>
#include <cmath>


using namespace std;

#define point pair <double, double>
#define x first
#define y second

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

const int NMAX = 1505;
const double eps = 0.0000001;
const double R3 = 1.73205080;

int N; point V[NMAX];

double abs(double X){
    return X > 0 ? X : -X;
}

int search(point A, int st, int dr) {

    if(st > dr) return 0;
    int pos = st; int step = 1;
    for(; step <= dr; (step <<= 1));

    for(pos = st; step; (step >>= 1))
        if( pos + step <= dr && (V[pos + step].x < A.x || ((A.x - V[pos +step].x) < eps && V[pos + step].y <= A.y )))
           pos += step;
    if((V[pos].x - A.x) < eps && (V[pos].y - A.y) < eps)
        return 1;
    return 0;
}

int main() {

    fin >> N;
    for(int i = 1 ; i <= N; ++i) {
        double a; double b;
        fin >> a >> b;
        V[i] = make_pair(a, b);
    }
    sort(V + 1, V + 1 + N);

    int count = 0;

    for(int i = 1; i < N; ++i) {
        for(int j = i + 1; j <= N; ++j) {

            double newX = (V[i].x + V[j].x + R3 * V[i].y - V[j].y * R3) * 0.5;
            double newY = (V[i].y + V[j].y - R3 * V[i].x + R3 * V[j].x) * 0.5;

            count += search(make_pair(newX, newY), j + 1, N);

            newX = (V[i].x + V[j].x - R3 * V[i].y + V[j].y * R3) * 0.5;
            newY = (V[i].y + V[j].y + R3 * V[i].x - R3 * V[j].x) * 0.5;

            count += search(make_pair(newX, newY), j + 1, N);

        }
    }

    fout << count << '\n';

    return 0;
}