Cod sursa(job #782698)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 29 august 2012 01:33:48
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

#define MAX 2048
#define EQL 1e-3
#define PI 3.14159265
#define sin60 sin(PI / 3)
#define cos60 cos(PI / 3)
#define X first
#define Y second
#define pb push_back
#define mp make_pair

using namespace std;

vector< pair < double , double > > v;
int n, sol;
double a, b, x, y;

inline bool equal(double x, double y)
{
    return fabs(x - y) < EQL;
}

inline bool Less(double x, double y)
{
    return x + EQL < y;
}

bool cmp(pair< double , double > a, pair< double , double > b)
{
    if(equal(a.X, b.X))
        return Less(a.Y, b.Y);
    return Less(a.X, b.X);
}

inline bool exist(int left, int right, double x, double y)
{
    while(left <= right)
    {
        int m = (left + right) >> 1;
        if(equal(v[m].X, x))
        {
            if(equal(v[m].Y, y))
                return true;
            else if(Less(v[m].Y, y))
                left = m + 1;
            else
                right = m - 1;
        }
        else if(Less(v[m].X, x))
            left = m + 1;
        else
            right = m - 1;
    }
    return false;
}

int main()
{
    ifstream in("triang.in");
    in>>n;
    for(int i = 1; i <= n; i++)
    {
        in>>a>>b;
        v.pb(mp(a, b));
    } in.close();
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < n - 2; i++)
        for(int j = i + 1; j < n - 1; j++)
        {
            x = v[i].X + (v[j].X - v[i].X) * cos60 - (v[j].Y - v[i].Y) * sin60;
            y = v[i].Y + (v[j].X - v[i].X) * sin60 + (v[j].Y - v[i].Y) * cos60;
            if(exist(j + 1, n - 1, x, y))
                sol++;
            x = v[i].X + (v[j].X - v[i].X) * cos60 + (v[j].Y - v[i].Y) * sin60;
            y = v[i].Y - (v[j].X - v[i].X) * sin60 + (v[j].Y - v[i].Y) * cos60;
            if(exist(j + 1, n - 1, x, y))
                sol++;
        }
    ofstream out("triang.out"); out<<sol; out.close();
}