Cod sursa(job #331467)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 14 iulie 2009 09:29:07
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

int i,j,n,m,k,x,y,nr;

struct nod
{ 
       float x,y;
}a[1520];

float p( float x)
{ 
    return x*x;
}

float lung( float x1, float y1,float x2, float y2) 
{ 
      return (p(x2-x1)+p(y2-y1));
}

int cautbin(int i,int j,float x,int k)
{ float l,l2;
    int st=k,dr=n,mij;
    while(st<=dr) { mij=(st+dr)/2;
                    l=lung(a[mij].x,a[mij].y,a[i].x,a[i].y);
                    l2=lung(a[mij].x,a[mij].y,a[j].x,a[j].y);
                    if(l==x&&l2==x) return  mij;
                    else if(x>l) st=mij+1;
                    else if(x<l) dr=mij-1;
                    else return 0;
                  }
   return 0;
}

bool comp(nod a,nod b)
{ 
     if(a.x!=b.x) return a.x<b.x;
     else return  a.y<b.y;
}

int main()
{ 
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    
    scanf("%d",&n);
    
    for(i=1;i<=n;i++) scanf("%f %f",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,comp);
    
    for(i=1;i<=n;i++) 
       for(j=i+1;j<=n;j++) { k=j+1;
                             while(k) { k=cautbin(i,j,lung(a[j].x,a[j].y,a[i].x,a[i].y),k);
                                        if(k) { k++;
                                                nr++;
                                              }
                                      }                                        
                           }
   printf("%d\n",nr);
   fclose(stdin);
   fclose(stdout);
   return 0;
}