Cod sursa(job #547852)

Utilizator ariel_roAriel Chelsau ariel_ro Data 6 martie 2011 19:06:54
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.37 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define NX 1505

FILE *in = fopen("triang.in", "r");
FILE *out = fopen("triang.out", "w");

int N, Res;
const double epsX = - (double)1 / 2, epsY = sqrt(3) / 2, EPS = pow(10, -3);

struct Punct
{
    double x, y;
};

const Punct eps = { epsX, epsY};

Punct pct[NX];

void cit()
{
    fscanf(in, "%d", &N);
    for (int i = 0; i < N; i++)
        fscanf(in, "%lf %lf", &pct[i].x, &pct[i].y);
}

Punct calcC1(Punct a, Punct b)
{
    Punct c;
    // var 1
    c.x = - (a.x * eps.x - a.y * eps.y) - (b.x * eps.x + b.y * eps.y);
    c.y = - (a.x * eps.y + a.y * eps.x) - (b.x * -eps.y + b.y * eps.x);
    return c;
}

Punct calcC2(Punct a, Punct b)
{
    Punct c;
    c.x = - (b.x * eps.x - b.y * eps.y) - (a.x * eps.x + a.y * eps.y);
    c.y = - (b.x * eps.y + b.y * eps.x) - (a.x * -eps.y + a.y * eps.x);
    return c;
}

double abs(double num) {
   return ( (num<0) ? num*(-1) : num);
}

bool points_sorter(const Punct &lhs, const Punct &rhs) {
    if (abs(lhs.x - rhs.x) > EPS) // lhs.x != rhs.x
        return lhs.x < rhs.x;
    return lhs.y < rhs.y;
}

int isPointFound(Punct c, int ind, int direction)
{
    double difPctXInd = pct[ind].x - c.x;
    while (abs(difPctXInd) < EPS && ind > -1 && ind < N) // pct[m].x == c.x
    {
        if (abs(pct[ind].y - c.y) < EPS) // pct[m].y == c.y
            return 1;

        if (direction == -1) // down
            ind--;
        else
            if (direction == 1) // up
                ind++;
        difPctXInd = pct[ind].x - c.x;
    }
    return 0;
}

int findC(Punct c)
{
    int p = 0, u = N - 1, m = 0;
    while (p <= u)
    {
        m = (p + u) >> 1;
        double difPctX = pct[m].x - c.x;
        if (abs(difPctX) > EPS && pct[m].x < c.x)// pct[m].x < c.x
            p = m + 1;
        else
        {
            if (abs(difPctX) > EPS && pct[m].x > c.x) // pct[m].x > c.x
                u = m - 1;
            else
                if (abs(difPctX) < EPS) // pct[m].x == c.x
                {
                    int ind = m;
                    double difPctY = pct[m].y - c.y;
                    if (abs(difPctY) > EPS && pct[m].y > c.y)
                    {
                        return isPointFound(c, ind, -1);
                    }
                    else
                    {
                        if (abs(difPctY) > EPS && pct[m].y < c.y) // pct[m].y > c.y
                        {
                            return isPointFound(c, ind, 1);
                        }
                        else
                        {
                            if (abs(difPctY) < EPS) // equality
                                return 1;
                        }
                    }
                }
        }
    }
    return 0;
}

int solve()
{
    Punct a, b, c1, c2;
    int total = 0;
    for (int i = 0; i < N - 1; i++)
    {
        a = pct[i];
        for (int j = i + 1; j < N; j++)
        {
            b = pct[j];
            c1 = calcC1(a, b);
            total += findC(c1);
            c2 = calcC2(a, b);
            total += findC(c2);
        }
    }

    return total;
}

int main()
{
    cit();
    sort(pct, pct + N, points_sorter);
    fprintf(out, "%d", solve() / 3);
    return 0;
}