Cod sursa(job #771182)

Utilizator gicu_01porcescu gicu gicu_01 Data 25 iulie 2012 01:10:12
Problema Triang Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct punct{
  double x;
  double y;
} a[1501];

int n;

void sw(double *a,double *b)
{
    double t=*a; *a=*b; *b=t;
}

void qs(int left,int right)
{
    int i,j; double p;
    i=left; j=right; p=a[(i+j)/2].x;
    while (i<j)
    {
        while (a[i].x<p) i++;
        while (a[j].x>p) j--;
        if (i<=j) {sw(&a[i].x,&a[j].x); sw(&a[i].y,&a[j].y); i++; j--;}
    }
    if (i<right) qs(i,right);
    if (j>left) qs(left,j);
}


int egal(double a,double b)
{
    if (abs(a-b)<=0.001) return 1; else return 0;
}


int cautare_bin(float x,int left,int right)
{
    int i,j,p;
    i=left; j=right; p=(i+j)/2;
    //printf("%i %i %i %lf\n",i,j,p,x);
    if (i==j)
    {
        if (egal(x,a[i].x)) return i; else return -1;
    } else
    if (x>=a[i].x && x<=a[p].x) cautare_bin(x,i,p); else
    if (x<=a[j].x  && x>=a[p+1].x) cautare_bin(x,p+1,j); else return -2;
}

int main()
{
    int i,j,x2,k=0; double x1,y1;
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    scanf("%i",&n);
    for (i=1; i<=n; i++) scanf("%lf%lf",&a[i].x,&a[i].y);
    qs(1,n);
    //for (i=1; i<=n; i++) printf("%lf %lf\n",a[i].x,a[i].y);
    for (i=1; i<=n-2; i++)
    {
        for (j=i+1; j<=n-1; j++)
        {
            x1=a[i].x+(a[j].x-a[i].x)*0.5-(a[j].y-a[i].y)*sqrt(3)/2;
            y1=a[i].x+(a[j].x-a[i].x)*sqrt(3)/2+(a[j].y-a[i].y)*0.5;
            x2=cautare_bin(x1,j+1,n);
            if (x2>0)
            {
                while (egal(x1,a[x2].x))
                {
                    if (egal(a[x2].y,y1)) {k++; break;}
                    x2++;
                }
            }
      //      printf("%lf %lf  %lf %lf  %lf %lf %i %i\n",a[i].x,a[i].y,a[j].x,a[j].y,x1,y1,x2,k);

            x1=a[i].x+(a[j].x-a[i].x)*0.5-(a[j].y-a[i].y)*(-0.866025403);
            y1=a[i].x+(a[j].x-a[i].x)*(-0.866025403)+(a[j].y-a[i].y)*0.5;
            x2=cautare_bin(x1,j+1,n);
            if (x2>0)
            {
                while (egal(x1,a[x2].x))
                {
                    if (egal(a[x2].y,y1)) {k++; break;}
                    x2++;
                }
            }
        //    printf("%lf %lf  %lf %lf  %lf %lf %i %i\n",a[i].x,a[i].y,a[j].x,a[j].y,x1,y1,x2,k);

        }
    }
    printf("%i",k);
    return 0;
}