Cod sursa(job #1865059)

Utilizator robx12lnLinca Robert robx12ln Data 1 februarie 2017 11:54:57
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<fstream>
#include<algorithm>
#define x first
#define y second
#define EPS 0.001
#define sin 0.866025
#define cos 0.500000
using namespace std;
ifstream fin("triang.in");
ofstream fout("triang.out");
int n, sol;
pair<double, double> v[1505], P;

double modul( double a ){
    return a >= 0 ? a : -a;
}

int bin_search( pair<double, double> p ){
    int st = 1;
    int dr = n;
    while( st <= dr ){
        int mid = ( st + dr ) / 2;
        if( modul( v[mid].x - p.x ) <= EPS && modul( v[mid].y - p.y ) <= EPS ){
            return 1;
        }
        if( ( modul( v[mid].x - p.x ) <= EPS && v[mid].y < p.y ) || v[mid].x < p.x ){
            st = mid + 1;
        }else{
            dr = mid - 1;
        }
    }
    return 0;
}

int main(){
    fin >> n;
    for( int i = 1; i <= n; i++ ){
        fin >> v[i].x >> v[i].y;
    }
    sort( v + 1, v + n + 1 );
    for( int i = 1; i <= n; i++ ){
        for( int j = i + 1; j <= n; j++ ){
            P.x = v[i].x + ( v[j].x - v[i].x ) * cos - ( v[j].y - v[i].y ) * sin;
            P.y = v[i].y + ( v[j].x - v[i].x ) * sin + ( v[j].y - v[i].y ) * cos;
            sol += bin_search( P );
            P.x = v[i].x + ( v[j].x - v[i].x ) * cos + ( v[j].y - v[i].y ) * sin;
            P.y = v[i].y - ( v[j].x - v[i].x ) * sin + ( v[j].y - v[i].y ) * cos;
            sol += bin_search( P );
        }
    }
    fout << sol / 3;
    return 0;
}