Cod sursa(job #1021779)

Utilizator Dayanna000Amegica Dayanna Dayanna000 Data 4 noiembrie 2013 11:11:34
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <math.h>
using namespace std;
double x[1501],y[1501],xt,yt,p,q;
int n,i,j,h,nr=0,ok;
void qs(int st, int dr)
  {
       double piv,aux,a,b,c,mi,ma;
       int i,j;
       i=st;
       j=dr;
       a=x[rand()%(j-i+1)+i];
       b=x[rand()%(j-i+1)+i];
       c=x[rand()%(j-i+1)+i];
       if(a<=b && a<=c)
          mi=a;
       if(b<=a && b<=c)
          mi=b;
       if(c<=a && c<=b)
          mi=c;
       if(a>=b && a>=c)
          ma=a;
       if(b>=a && b>=c)
          ma=b;
       if(c>=a && c>=b)
          ma=c;
      piv=a+b+c-mi-ma;
      while(i<=j)
      {
       while(x[i]<piv)
          i++;
       while(x[j]>piv)
          j--;
        if(i<=j)
        {
           aux=x[i];
           x[i]=x[j];
           x[j]=aux;
           aux=y[i];
           y[i]=y[j];
           y[j]=aux;
           i++;
           j--;
         }
      }
    if(st<j)
       qs(st,j);
    if(i<dr)
       qs(i,dr);
    }
int caut(double r, int st, int dr)
  {
      int poz,k=1;
       while(st<=dr)
         {
             poz=(st+dr)/2;
             if(x[poz]==r)
                {
                    k=poz;
                    while(x[poz+1]==r)
                       poz++;
                    k=poz;
                    return k;
                }
                else
             if(x[poz]<r)
               st=poz+1;
               else
               {
                   k=poz;
                   dr=poz-1;
               }

         }
       return k;

  }
double pam(double pp)
  {
      int h1;
      double qq;
      qq=pp*1000;
      h1=qq;
      return (double)h1/1000;

  }
int main()
{
    ifstream f("triang.in");
    ofstream g("triang.out");
    f>>n;
    for(i=1;i<=n;i++)
          f>>x[i]>>y[i];

    qs(1,n);
    for(i=1;i<=n-1;i++)
          for(j=i+1;j<=n;j++)
             {
                xt=x[i]+(x[j]-x[i])*1/2-(y[j]-y[i])*(sqrt(3)/2);
                yt=y[i]+(x[j]-x[i])*(sqrt(3)/2)+(y[j]-y[i])*1/2;
                p=pam(xt);
                q=pam(yt);
                ok=0;
                h=caut(p,1,n);
                if(pam(x[h]-p)==0)
                    {
                        if(pam(y[h]-q)==0)
                             ok=1;
                        while(h>1 && pam(x[h-1]-p)==0)
                           {
                               if(pam(y[h-1]-q)==0)
                                    ok=1;
                               h--;
                           }
                        if(ok==1)
                          nr++;
                    }
             }
    cout<<nr<<"  ";
    f.close();
    g.close();
    return 0;
}