Cod sursa(job #822618)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 23 noiembrie 2012 20:28:00
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<fstream>
#include<algorithm>
#include<math.h>

using namespace std;

#define MAXN 1502
#define EPS 0.001
#define PI 3.1415926535


typedef struct { double x, y; } point;
int n, i, j, res, t;
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( fabs(A.x - v[mid].x) < EPS && fabs(A.y - v[mid].y) < EPS)
            return mid;
        else if( v[mid].x - A.x > EPS || ( (fabs(A.x - v[mid].x) < EPS) && v[mid].y - A.y > EPS) )
            end = mid - 1;
        else st = mid + 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(PI/3) - (Y2 - Y1) * sin(PI/3);
            P.y = Y1 + (X2 - X1) * sin(PI/3) + (Y2 - Y1) * cos(PI/3);
            t = bs(P);
            if(t > j)
                ++res;

            P.x = X1 + (X2 - X1) * cos(-PI/3) - (Y2 - Y1) * sin(-PI/3);
            P.y = Y1 + (X2 - X1) * sin(-PI/3) + (Y2 - Y1) * cos(-PI/3);

            t = bs(P);
            if(t > j)
                ++res;

        }

    ofstream g("triang.out");

    g << res << endl;

    g.close();

    return 0;
}