Cod sursa(job #199946)

Utilizator CezarMocanCezar Mocan CezarMocan Data 21 iulie 2008 14:08:35
Problema Triang Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

struct juma_de_marmota{double x; double y;};

juma_de_marmota v[1520],t41,t42,t3;
long n,i,j,nr,rez;
double a,b,p,q,ab,d;

inline bool egal(double a, double b)
    {
    if (abs(a-b)<0.0001)
        return true;
    else
        return false;    
    }

bool mai_mic(juma_de_marmota a, juma_de_marmota b)
    {
    if (a.x-b.x<(-0.0001))
        return true;
    if (egal(a.x,b.x)&&(a.y-b.y<(-0.0001)))
        return true;
    return false;    
    }

bool cmp(juma_de_marmota a, juma_de_marmota b)
    {
    if (mai_mic(a,b))
        return true;
    else    
        return false;
    }
    
double dist(juma_de_marmota a, juma_de_marmota b)
    {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));    
    }
        
long bsearch(juma_de_marmota p, long l, long r)
    {
    long m=(l+r)/2;
    if (egal(p.x,v[m].x))
        return 1;
    if (l>=r)
        return 0;
    if (mai_mic(p,v[m]))
        return bsearch(p,l,m-1);
    else
        return bsearch(p,m+1,r);    
    }

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++)
        {
        a=v[i].y-v[j].y;
        b=v[i].x-v[j].x;
        t3.x=(v[i].x+v[j].x)/2;
        t3.y=(v[i].y+v[j].y)/2;
        if (a==0||b==0)
            {
            ab=dist(v[i],v[j]);
            d=ab*sqrt(3.0)/2;
            if (a==0)
                {
                t41.x=t3.x;
                t41.y=t3.y+d;    
                t42.x=t3.x;
                t42.y=t3.y-d;    
                }    
            else
                {
                t41.x=t3.x+d;
                t41.y=t3.y;    
                t42.x=t3.x-d;
                t42.y=t3.y;                        
                }
            }
        else
            {
            ab=dist(v[i],v[j]);
            d=ab*sqrt(3.0)/2;
            q=sqrt(d*d/((-b/a)*(-b/a)+1));    
            if (a==0)
                p=b;
            else
                p=-b/a*q;
            t41.y=t3.y-p;
            t41.x=t3.x-q;
            q=-q;
            p=-p;
            t42.y=t3.y-p;
            t42.x=t3.x-q;        
            }
        rez+=bsearch(t41,j+1,n);
        rez+=bsearch(t42,j+1,n);
        }
printf("%d\n",rez);
return 0;
}