Cod sursa(job #1081298)

Utilizator Catalina_BrinzaBrinza Catalina Catalina_Brinza Data 13 ianuarie 2014 15:07:07
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 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 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;
        if(abs(x.a-y.a)<0.0001)
        {
            if(abs(x.b-y.b)<0.0001) return 1;
            else
                if(x.b>y.b) f=m-1;
                else return i=m+1;
        }
        if (f!=m-1 && i!=m+1){
        if(x.a>y.a) f=m-1;
        else i=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)
        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);

           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);
 
            s+=caut(x);
       
        }
    s/=3LL;
    out<<s<<"\n";
    return 0;
}