Cod sursa(job #473097)

Utilizator ionutz32Ilie Ionut ionutz32 Data 27 iulie 2010 23:31:59
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

struct punct
{
    double x,y;
} v[1505];
struct cmp
{
    inline bool operator()(const punct &a,const punct &b)const
    {
        if (a.x<b.x)
            return 1;
        if (a.x==b.x)
            return (a.y<=b.y);
        return 0;
    }
};
double c,d,diag1,diag2,c2,d2,a,b,latmare,latmica;
int n,i,j,t,p,u,m,nr,ret;
bool k;

inline int comp(double x,double y)
{
    if (abs(x-y)<=0.001)
        return 0;
    if (x>y)
        return 1;
    return 2;
}

int main()
{
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
        scanf("%lf %lf",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp());
    for (i=1;i<=n-2;++i)
        for (j=i+1;j<=n-1;++j)
        {
            c=abs(v[j].x-v[i].x);
            d=abs(v[j].y-v[i].y);
            diag2=sqrt(c*c+d*d);
            diag1=diag2*sqrt(3)/2;
            diag2/=2;
            c2=(v[i].x+v[j].x)/2;
            d2=(v[i].y+v[j].y)/2;
            d=abs(c2-v[i].x);
            c=abs(d2-v[i].y);
            latmare=c*diag1/diag2;
            latmica=d*diag1/diag2;
            if ((v[j].x>v[i].x && v[j].y>v[i].y) || (v[i].x>v[j].x && v[i].y>v[j].y))
            {
                a=c2-latmare;
                b=d2+latmica;
                c2+=latmare;
                d2-=latmica;
            }
            else
            {
                a=c2+latmare;
                b=d2+latmica;
                c2-=latmare;
                d2-=latmica;
            }
            p=j+1;
            u=n;
            while (p<=u)
            {
                m=p+((u-p)>>1);
                ret=comp(v[m].x,c2);
                if (ret==1 || (!ret && comp(v[m].y,d2)<2))
                    u=m-1;
                else
                    p=m+1;
            }
            if (!comp(v[u+1].x,c2) && !comp(v[u+1].y,d2))
                ++nr;
        }
    printf("%d",nr);
    return 0;
}