Cod sursa(job #1081314)

Utilizator Catalina_BrinzaBrinza Catalina Catalina_Brinza Data 13 ianuarie 2014 15:22:18
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>
#include <cmath>
#define nru 1501

using namespace std;
ofstream out("triang.out");
ifstream in("triang.in");
int n;

struct ind
{
    double a,b;
};
ind v[nru];

void quicksort(int f,int n)
{
    int i=f, j=n,p=f;
    while(i<=j)
    {
        while(v[i].a<v[p].a)
            i++;
        while(v[j].a>v[p].a)
            j--;
        if(i<=j)
        {
            swap(v[i],v[j]);
            if(v[i].a==v[j].a)
                if(v[i].b>v[j].b)swap(v[i].b,v[j].b);
            i++;
            j--;
        }
        
    }
    if(f<j)
        quicksort(f,j);
    if(i<n)
        quicksort(i,n);
}

int com(ind x, ind y)
{
    if(abs(x.a-y.a)<0.0001)
    {
        if(abs(x.b-y.b)<0.0001) return 0;
        else
            if(x.b>y.b) return 1;
            else return -1;
    }
    if(x.a>y.a) return 1;
    else return -1;
}

int caut(ind x)
{
    int i=1,f=n,m,ok;
    ind y;
    while(i<=f)
    {
        m=i+(-i+f)/2;
        y.a=v[m].a; y.b=v[m].b;
        ok=com(x,y);
        if(ok==0) return 1;
        if(ok<0) i=m+1;
        else f=m-1;
    }
    return 0;
}

int main()
{
    int i,j;
    ind x;
    long long s=0;
    in>>n;
    for(int i=1;i<=n;++i)
        in>>v[i].a>>v[i].b;
    quicksort(1,n);
 //   for (i=1;i<=n;++i) out<<v[i].a<<' '<<v[i].b<<"\n";
   for(i=1;i<n;++i)
        for(j=i+1;j<=n;++j)
        {
            
           x.a=(v[j].a+v[i].a)*0.5-sqrt(3.0)*0.5*(v[j].b-v[i].b);
        x.b=(v[j].b+v[i].b)*0.5+sqrt(3.0)*0.5*(v[j].a-v[i].a);
           // out<<x.a<<' '<<x.b<<"\n";
            s+=caut(x);

            x.a=(v[j].a+v[i].a)*0.5+sqrt(3.0)*0.5*(v[j].b-v[i].b);
            x.b=(v[j].b+v[i].b)*0.5-sqrt(3.0)*0.5*(v[j].a-v[i].a);
            //out<<x.a<<' '<<x.b<<"\n";
            s+=caut(x);
       
        }
    out<<s<<"\n";
    return 0;
}