Cod sursa(job #771086)

Utilizator gicu_01porcescu gicu gicu_01 Data 24 iulie 2012 18:51:05
Problema Triang Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.76 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;
    //printf("%i %i\n",i,j);
    if (i==j)
     {
         if (egal(a[i].x,x)) return i; else return -2;
     } else
    if (x>=a[i].x && x<=a[r].x) cautare_bin(x,i,r); else
    if (x>=a[r+1].x && x<=a[j].x) cautare_bin(x,r+1,j); else return -1;
}


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);
            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;
}