Cod sursa(job #592007)

Utilizator darrenRares Buhai darren Data 26 mai 2011 12:35:31
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <cmath>
#include <fstream>
#include <algorithm>

using namespace std;

#define x first
#define y second

const double CONST = sqrt(3);
const double eps = 0.0001;

int N, triang;
pair<double, double> P[1502];

int compare(const pair<double, double>& p1, const pair<double, double>& p2)
{
    if (p1.x - p2.x < -eps) return 0;
    if (p2.x - p1.x < -eps) return 2;
    if (p1.y - p2.y < -eps) return 0;
    if (p2.y - p1.y < -eps) return 2;
    return 1;
}
bool sortcomp(const pair<double, double>& p1, const pair<double, double>& p2)
{
    if (fabs(p1.x - p2.x) < eps)
        return (p1.y - p2.y < -eps);
    return (p1.x - p2.x < -eps);
}

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

    fin >> N;
    for (int i = 1; i <= N; ++i)
        fin >> P[i].x >> P[i].y;

    sort(P + 1, P + N + 1, sortcomp);

    int logN, step, now;
    for (logN = 1; (logN << 1) <= N; logN <<= 1);

    for (int i = 1; i <= N; ++i)
        for (int j = i + 1; j <= N; ++j)
        {
            pair<double, double> mid;
            mid.x = (P[i].x + P[j].x) / 2;
            mid.y = (P[i].y + P[j].y) / 2;

            pair<double, double> dist;
            dist.x = P[i].x - mid.x;
            dist.y = P[i].y - mid.y;
            dist.x *= CONST, dist.y *= CONST;

            pair<double, double> point1, point2;
            point1.x = mid.x + dist.y;
            point1.y = mid.y + dist.x;
            point2.x = mid.x - dist.y;
            point2.y = mid.y - dist.x;

            // point1
            step = logN;
            for (now = 0; step; step >>= 1)
                if (now + step <= N && compare(P[now + step], point1) != 2)
                    now += step;

            triang += (compare(P[now], point1) == 1);

            // point2
            step = logN;
            for (now = 0; step; step >>= 1)
                if (now + step <= N && compare(P[now + step], point2) != 2)
                    now += step;

            triang += (compare(P[now], point2) == 1);
        }

    fout << triang;

    fin.close();
    fout.close();
}