Cod sursa(job #805715)

Utilizator misinozzz zzz misino Data 31 octombrie 2012 22:38:40
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<fstream>
#include<algorithm>
#define R3 1.732050807568877
#define eps 150
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
int i,j,n,nr;
double x,y;
struct pc {int x,y;};
pc v[1505],a,b,c;
bool zero(int a)
{
    if(a>=-eps&&a<=eps)
    return 1;
    return 0;
}
bool cmp(pc a,pc b)
{
    if(zero(a.x-b.x))
    return a.y<=b.y;
    return a.x<=b.x;
}

void cauta(pc a)
{
    int li=j+1,ls=n,mij,sol;
    while(li<=ls)
    {
        mij=(li+ls)>>1;
        if(cmp(v[mij],a))
        {sol=mij;
        li=mij+1;
        }
        else
        ls=mij-1;
    }
    if(zero(v[sol].x-a.x)&&zero(v[sol].y-a.y))
    ++nr;
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>x>>y;
        v[i].x=x*100000;
        v[i].y=y*100000;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<n;++i)
    for(j=i+1;j<=n;++j)
    {
        a=v[i];
        b=v[j];
        c.x=a.x;
        c.x=c.x+(b.x-a.x)/2.0;
        c.x-=( b.y-a.y )*R3/2;
        c.y=a.y + (b.x-a.x)*R3/2 + (b.y-a.y)/2.0;
        cauta(c);
        c.x=a.x + (b.x-a.x)/2.0 + ( b.y-a.y )*R3/2;
        c.y=a.y - (b.x-a.x)*R3/2 + (b.y-a.y)/2.0;
        cauta(c);
    }
    g<<nr<<'\n';
    return 0;
}