Cod sursa(job #2130809)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 13 februarie 2018 22:13:09
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<fstream>
#include<algorithm>
#define EPS 1e-3
using namespace std;
ifstream fi("triang.in");
ofstream fo("trinag.out");
const double cos60=0.86602540378;
double x,y;
pair<double,double> A[1501];
int n,i,j,rez;

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

int bs(int st, double x, double y)
{
    int rez=st;
    int i;
    for(i=10; i>=0; i--)
    {
        int ind=rez+(1<<i);
        if(ind<=n)
        {
            if(modul(A[ind].first-x)<=EPS && modul(A[ind].second-y)<=EPS)
                return 1;
            if(A[ind].first<x || A[ind].second<y)
                rez=ind;
        }
    }
    if(modul(A[rez].first-x)<=EPS && modul(A[rez].second-y)<=EPS)
        return 1;
    return 0;
}

int main()
{
    fi>>n;
    for(i=1; i<=n; i++)
        fi>>A[i].first>>A[i].second;
    sort(A+1,A+n+1);
    for(i=1; i<=n-2; i++)
    {
        for(j=i+1; j<=n-1; j++)
        {
            x=((A[i].first+A[j].first)/2)+(cos60*(A[j].second-A[i].second));
            y=((A[i].second+A[j].second)/2)+(cos60*(A[i].first-A[j].first));
            rez+=bs(j+1,x,y);
            x=((A[i].first+A[j].first)/2)+(cos60*(A[i].second-A[j].second));
            y=((A[i].second+A[j].second)/2)+(cos60*(A[j].first-A[i].first));
            rez+=bs(j+1,x,y);
        }
    }
    fo<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
}