Cod sursa(job #822378)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 23 noiembrie 2012 13:56:01
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<fstream>
#include<algorithm>
#include<math.h>

using namespace std;

#define MAXN 1502
#define EPS 0.001
#define sin_60 0.866
#define cos_60 0.5


typedef struct { double x, y; } point;
int n, i, j, res;
double X1, Y1, X2, Y2;
point P;
point v[ MAXN ];

inline int cmp(point A, point B)
{
    if(A.x > B.x)
        return 0;
    if( fabs(A.x - B.x) < EPS && A.y > B.y)
        return 0;
    return 1;
}

inline int bs(point A)
{
    int st = 1, end = n, mid;

    while(st <= end)
    {
        mid = (st + end) / 2;
        if(v[mid].x - A.x > EPS)
            end = mid - 1;
        else if(v[mid].x - A.x < -EPS)
            st = mid + 1;
        else
        {
            if(v[mid].y - A.y > EPS)
                end = mid - 1;
            else if(v[mid].y - A.y < -EPS)
                st = mid + 1;
            else return 1;
        }
    }
    return 0;
}

int main()
{
    ifstream f("triang.in");

    f >> n;
    for(i = 1; i <= n; ++i)
        f >> v[i].x >> v[i].y;

    f.close();

    sort(v+1, v+n+1, cmp);

    for(i = 1; i <= n; ++i)
        for(j = i + 1; j <= n; ++j)
        {
            X1 = v[i].x, Y1 = v[i].y;
            X2 = v[j].x, Y2 = v[j].y;

            P.x = X1 + (X2 - X1) * cos_60 - (Y2 - Y1) * sin_60;
            P.y = Y1 + (X2 - X1) * sin_60 - (Y2 - Y1) * cos_60;
            res += bs(P);

            P.x = X1 + (X2 - X1) * (-cos_60) - (Y2 - Y1) * (-sin_60);
            P.y = Y1 + (X2 - X1) * (-sin_60) - (Y2 - Y1) * (-cos_60);
            res += bs(P);

        }

    ofstream g("triang.out");

    g << res << endl;

    g.close();

    return 0;
}