Cod sursa(job #770962)

Utilizator gicu_01porcescu gicu gicu_01 Data 24 iulie 2012 14:14:19
Problema Triang Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct punct{
  float x;
  float y;
} a[1501];

int n;

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

void qs(int left,int right)
{
    int i,j; float 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(float a,float b)
{
    if (a-b<0.001) return 1; else return 0;
}


int cautare_bin(float x,int left,int right)
{
    int i,j,r;
    i=left; j=right; r=(i+j)/2;
    if (i==j-1)
     {
         if (egal(a[j].x,x)) return j; else
         if (egal(a[i].x,x)) return i; else return j;
     } else
    if (x>=a[i].x&& x<=a[r].x) cautare_bin(x,i,r); else
    if (x>=a[r].x && x<=a[j].x) cautare_bin(x,r,j); else return i;
}


int main()
{
    int i,j,x2,k=0; float x1,y1;
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);

    scanf("%i",&n);
    for (i=1; i<=n; i++) scanf("%f%f",&a[i].x,&a[i].y);
    qs(1,n);
    for (i=1; i<n; i++)
    {
        for (j=i+1; j<=n; 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,1,n);
    //        printf("%i",x2);
            while (x1==a[x2].x)
            {
                if (egal(a[x2].y,y1)) {k++; break;}
                x2++;
            }
        }
    }
    printf("%i",k);
    return 0;
}