Cod sursa(job #1435934)

Utilizator Athena99Anghel Anca Athena99 Data 14 mai 2015 19:44:59
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <algorithm>
#include <cmath>
#include <fstream>

using namespace std;

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

const int nmax= 1500;
const double prec= 0.001;

int n;

struct str {
    double x, y;
} v[nmax+1];

bool cmp( str x, str y ) {
    if ( x.x==y.x ) return x.y<y.y;
    return x.x<y.x;
}

bool egal( double a, double b ) {
    double x= (double)a-b;
    if ( x<0 ) x= -x;

    if ( x<prec ) return 1;
    return 0;
}

bool find( double x, double y ) {
    int left= 1, right= n, mid;
    while ( left<=right ) {
        mid= (left+right)/2;
        if ( egal(v[mid].x, x) ) {
            if ( egal(v[mid].y, y) ) return 1;
            if ( v[mid].y<y ) left= mid+1;
            else right= mid-1;
        } else {
            if ( v[mid].x<x ) left= mid+1;
            else right= 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, cmp );

    double sq3= (double)sqrt(3);
    int sol= 0;
    for ( int i= 1; i<=n-1; ++i ) {
        for ( int j= i+1; j<=n; ++j ) {
            str ans[2];
            ans[0].x= (v[i].x+v[j].x+(v[i].y-v[j].y)*sq3)/2;
            ans[0].y= (v[i].y+v[j].y+(v[j].x-v[i].x)*sq3)/2;
            ans[1].x= (v[i].x+v[j].x+(v[j].y-v[i].y)*sq3)/2;
            ans[1].y= (v[i].y+v[j].y+(v[i].x-v[j].x)*sq3)/2;

            if ( find(ans[0].x, ans[0].y) ) ++sol;
            if ( find(ans[1].x, ans[1].y) ) ++sol;
        }
    }

    sol/= 3;
    fout<<sol<<"\n";

    return 0;
}