Cod sursa(job #337544)

Utilizator xtremespeedzeal xtreme Data 3 august 2009 22:32:02
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <iostream.h>
#include <fstream.h>
#include <math.h>
#include <algorithm>
#define nmax 1501
#define precizie 0.001
using namespace std;

ifstream in("triang.in");
ofstream out("triang.out");

struct puncte  {double x,y;} p[nmax],pc;
int n,i,j,rez;
double l;

int cautbin(int ic,int sf)
     {int mij,m;
      while(ic<=sf)
          {mij=(ic+sf)/2;
           if(p[mij].y-pc.y<precizie)
                        {for(m=mij;m<=n;m++)
                                 {if(p[m].y-pc.y<precizie)   if(p[m].x-pc.x<precizie)     return 1;
                                  else                       break;}     
                         for(m=mij-1;m>j;m--)
                                 {if(p[m].y-pc.y<precizie)   if(p[m].x-pc.x<precizie)     return 1;
                                  else                       break;}
                        }
           else if(p[mij].y>pc.y)                 sf=mij-1;
           else                                   ic=mij+1;
          }
      return 0;
      }
bool cmp(puncte a,puncte b)    {return a.y<b.y;}
int main()
    {in>>n;
     for(i=1;i<=n;i++)   in>>p[i].x>>p[i].y;
     sort(p+1,p+1+n,cmp);
     for(i=1;i<=n-2;i++)
        for(j=i+1;j<=n-1;j++)
              {l=p[i].x*p[i].x-2*p[i].x*p[j].x+p[j].x*p[j].x+p[i].y*p[i].y-2*p[i].y*p[j].y+p[j].y*p[j].y;
               l=sqrt(l);pc.x=(p[i].x+p[j].x)/2;pc.y=(p[i].y+p[j].y)/2+(l*sqrt(3))/2;
               rez+=cautbin(j+1,n);
               }
    out<<rez;in.close();out.close();return 0;
    }