Cod sursa(job #337530)

Utilizator xtremespeedzeal xtreme Data 3 august 2009 22:04:51
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream.h>
#include <fstream.h>
#include <math.h>
#include <algorithm>
#define nmax 1501
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,mar;
      while(ic<=sf)
          {mij=(ic+sf)/2;
           if(p[mij].y-pc.y<0.00001)
                        {mar=mij;do   {if(p[mar].y-pc.y<0.00001)      return 1;
                                      mar--;
                                      }while(p[mar].y-pc.y<0.00001);
                         mar=mij;do   {if(p[mar].y-pc.y<0.00001)      return 1;
                                      mar++;
                                      }while(p[mar].y-pc.y<0.00001);
                        }
           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;i++)
        for(j=i+1;j<=n;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;
    }