Cod sursa(job #1463838)

Utilizator borcanirobertBorcani Robert borcanirobert Data 21 iulie 2015 16:22:33
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

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

const int MAX = 1550;
const float eps = 0.001;
struct Punct{
    float x, y;
};
int N;
Punct P[MAX];
Punct P1, P2, P3;
float sina, cosa;
int nrp;
float L, d;
float x, y, xx, yy;

void Read();
void NrTri();
int Egl( Punct a, Punct b );
bool BinarySearch( int l, Punct p );

float Abs( float a )
{
    if ( a >= 0 )
        return a;
    return -a;
}

bool Comp( const Punct& p1, const Punct& p2 )
{
    if ( p1.x < p2.x || ( p1.x == p2.x && p1.y < p2.y ) )
        return true;
    return false;
}

int main()
{
    Read();
    NrTri();
    fout << nrp / 3 << '\n';
    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    int i;
    fin >> N;
    for ( i = 1; i <= N; i++ )
        fin >> P[i].x >> P[i].y;
    sort( P + 1, P + 1 + N, Comp );
}

void NrTri()
{
    int i, j;

    for ( i = 1; i < N; i++ )
        for ( j = i + 1; j <= N; j++ )
        {
            P1 = P[i]; P2 = P[j];
            L = sqrt( ( P1.x - P2.x )*( P1.x - P2.x ) + ( P1.y - P2.y )*( P1.y - P2.y ) );
            d = (sqrt(3) * L) / 2;
            sina = ( P2.y - P1.y ) / L;
            cosa = ( P2.x - P1.x ) / L;
            x = (( P2.x + P1.x ) / 2 ) - d*sina;
            y = (( P2.y + P1.y ) / 2 ) + d*cosa;
            xx = (( P2.x + P1.x ) / 2 ) + d*sina;
            yy = (( P2.y + P1.y ) / 2 ) - d*cosa;
         //   cout << x << ' ' << y << '\n' << xx << ' ' << yy;  cin.get();
      //      cout << fixed << setprecision(3) << ( P2.y + P1.y ) / 2 - d*cosa; cin.get();
      //      cout << fixed << setprecision(3) << yy; cin.get();
            P3.x = x, P3.y = y;
            if ( BinarySearch(1, P3) ) nrp++;       /// Caut de la pozitia j + 1 pentru ca sa nu mi
            P3.x = xx, P3.y = yy;
            if ( BinarySearch(1, P3) ) nrp++;
        }
}

int Egl( Punct a, Punct b )
{
  //  cout << Abs( a.x - b.y ); cin.get();
    if ( Abs(a.x - b.x) <= eps && Abs(a.y - b.y) <= eps )       /// Am gasit punctul cautat
        return 0;
    if ( a.x - b.x > eps || ( Abs(a.x - b.x) <= eps && a.y - b.y > eps ) )      /// Dupa cum am sortat sirul P, daca este indeplinita aceasta conditie
        return 1;                                                               /// inseamna ca punctul cautat se afla pe o pozitie mai mare

    return 2;                                                                   /// Altfel se afla pe o pozitie mai mica.
}

bool BinarySearch( int l, Punct p )
{
    int r = N, mid, x;
    while ( l <= r )
    {
        mid = ( l + r ) / 2;
        x = Egl( p, P[mid] );
        if ( x == 1 )
            l = mid + 1;
        else
            if ( x == 2 )
                r = mid - 1;
            else
                return true;
    }
    return false;
}