Cod sursa(job #748307)

Utilizator Athena99Anghel Anca Athena99 Data 13 mai 2012 00:21:32
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>
#include <math.h>

double x[1501],y[1501];

int bs(int n, double k, double m)
{
    int start=0,mid=n/2,stop=n-1;
    while (start<=stop)
    {
        if (x[mid]<k-0.001)
            start=mid+1;
        else if (x[mid]>k+0.001)
            stop=mid-1;
        else
        {
            if (y[mid]<m-0.001)
                start=mid+1;
            else if (y[mid]>m+0.001)
                stop=mid-1;
            else return 1;
        }
        mid=(start+stop)/2;
    }
    return 0;
}

int main()
{
    int i=0,j=0,poz=0,n=0,rez=0;
    double a1=0,a2=0,min=0,k=0,m=0;
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    scanf("%d",&n);
    for (i=0; i<n; ++i)
        scanf("%lf%lf",&y[i],&x[i]);
    for (i=0; i<n; ++i)
    {
        a1=x[i];
        a2=y[i];
        min=x[i];
        poz=i;
        for (j=i+1; j<n; ++j)
            if (min>x[j])
            {
                poz=j;
                min=x[j];
            }
        x[i]=x[poz];
        x[poz]=a1;
        y[i]=y[poz];
        y[poz]=a2;
    }
    for (i=0; i<n; ++i)
    {
        a1=y[i];
        min=y[i];
        poz=i;
        j=i+1;
        while (j<n && x[i]==x[j])
        {
            if (y[j]<min)
            {
                min=y[j];
                poz=j;
            }
            ++j;
        }
        y[i]=y[poz];
        y[poz]=a1;
    }
    for (i=0; i<n-2; ++i)
        for (j=i+1; j<n-1; ++j)
        {
            k=x[i]+fabs(x[j]-x[i])/2+(sqrt(3))/2*(y[j]-y[i]);
            m=y[i]+(y[j]-y[i])/2+sqrt(3)/2*fabs(x[j]-x[i]);
            rez+=bs(n,k,m);
        }
    printf("%d",rez);
    return 0;
}