Cod sursa(job #337461)

Utilizator xtremespeedzeal xtreme Data 3 august 2009 18:41:43
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 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;
      while(ic<=sf)
          {mij=(ic+sf)/2;
           if(p[mij].x-pc.x<0.001)      {rez++;return 0;}
           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=pow(p[i].x,2)-2*p[i].x*p[j].x+pow(p[j].x,2)+pow(p[i].y,2)-2*p[i].y*p[j].y+pow(p[j].y,2);
               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;
               cautbin(1,i-1);cautbin(j+1,n);
               }
    out<<rez/2;in.close();out.close();return 0;
    }