Cod sursa(job #474254)

Utilizator freak93Adrian Budau freak93 Data 3 august 2010 01:27:53
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#define punct pair<double,double>
#define x first
#define y second

using namespace std;

const char iname[]="triang.in";
const char oname[]="triang.out";
const int maxn=1505;

ifstream f(iname);
ofstream g(oname);

punct a[maxn];
double eps=1e-3,aux=sqrt(3);

int n,i,j,k,ans,step;

inline int cmp(double a,double b)
{
    if(a+eps<b)
        return -1;
    if(b+eps<a)
        return 1;
    return 0;
}

inline int cmp(punct a,punct b)
{
    int d=cmp(a.x,b.x);
    if(d)
        return d;
    return cmp(a.y,b.y);
}

punct get(punct a,punct b)
{
    return make_pair(0.5*((a.x+b.x)+aux*(a.y-b.y)),0.5*((b.y+a.y)+aux*(b.x-a.x)));
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;

    sort(a+1,a+n+1);
    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j)
        {
            punct aux=get(a[i],a[j]);
            if(cmp(aux,a[j])>0)
            {
                for(step=1;step<(n-j);step<<=1);
                for(k=j;step;step>>=1)
                    if(k+step<=n&&cmp(a[k+step],aux)<=0)
                        k+=step;
                if(cmp(a[k],aux)==0)
                    ++ans;
            }
            aux=get(a[j],a[i]);
            if(cmp(aux,a[j])>0)
            {
                for(step=1;step<(n-j);step<<=1);
                for(k=j;step;step>>=1)
                    if(k+step<=n&&cmp(a[k+step],aux)<=0)
                        k+=step;
                if(cmp(a[k],aux)==0)
                    ++ans;
            }
        }
    g<<ans<<"\n";
}