Cod sursa(job #1026088)

Utilizator vlad.florescu94FMI Florescu Vlad - Adrian vlad.florescu94 Data 11 noiembrie 2013 01:59:15
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include<fstream>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#define rad3 1.73205081
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
struct punct
  {
    double x,y;
  };

int n,nr=0,i,j,deb;
punct v[1501],test1,test2,mid;
double panta,a,b,c,eps=10e-4,aux1,aux2;

int cmp(punct a, punct b)
{
    if(a.x-b.x<eps&&a.x-b.x>-eps)
        {if(a.y-b.y<eps&&a.y-b.y>-eps)
            return 0;
        else
            if(a.y-b.y>eps)
                return 1;
        else return -1;
        }
    if(a.x-b.x>eps)
        return 1;
    return -1;
}

void qksort(int st,int dr)
{int p=st,q=dr;
 double temp;
 punct piv,aux;
 piv=v[p+rand()%(q-p+1)];
 while(p<=q)
   {
    while(v[p].x<piv.x)
        p++;
    while(v[q].x>piv.x)
        q--;
    if(p<=q)
      {
       aux=v[p];v[p]=v[q];v[q]=aux;
       if(v[p].x==v[q].x)
         if(v[p].y>v[q].y)
           {temp=v[p].y;v[p].y=v[q].y;v[q].y=temp;}
       p++;q--;
      }
   }
 /*for(deb=1;deb<=n;deb++)
    g<<v[deb].x<<" ";
 g<<'\n';
 for(deb=1;deb<=n;deb++)
    g<<v[deb].y<<" ";
 g<<'\n'<<'\n';*/
 if(st<q)
    qksort(st,q);
 if(p<dr)
    qksort(p,dr);
}

bool caut_bin(int st,int dr,punct k)
{int m;
   while(st<=dr)
     {
         m=(st+dr)/2;
         if(cmp(v[m],k)==0)
            return 1;
         else
            if(cmp(v[m],k)<0)
               st=m+1;
            else
               dr=m-1;
     }
  return 0;
}

void ec_gr2(double a,double b,double c)
{
  double delta=pow(b,2)-4*a*c;
  test1.x=(-b+sqrt(delta))/(2*a);
  test2.x=(-b-sqrt(delta))/(2*a);
}

int main()
{
  srand(time(0));
  f>>n;
  for(i=1;i<=n;i++)
    f>>v[i].x>>v[i].y;
  qksort(1,n);
  //g<<'\n'<<'\n';
  for(i=1;i<=n-1;i++)
    for(j=i+1;j<=n;j++)
      {
         mid.x=(v[i].x+v[j].x)/2;
         mid.y=(v[i].y+v[j].y)/2;
         if(v[j].y-v[i].y==0)
             {
                test1.x=test2.x=mid.x;
                test1.y=mid.y+rad3*mid.x;
                test2.y=mid.y-rad3*mid.x;
             }
         else
           {
  //g<<"panta e:"<<panta<<"  ";
         panta=(v[i].x-v[j].x)/(v[j].y-v[i].y);
         aux1=pow(v[j].y-v[i].y,2);
         aux2=pow(v[j].x-v[i].x,2);
         aux1+=aux2;
         a=1+pow(panta,2); //g<<"a="<<a<<" ";
         b=-2*v[i].x+2*panta*mid.y-2*pow(panta,2)*mid.x-2*panta*v[i].y;// g<<"b="<<b<<" ";
         c=pow(mid.y,2)+pow(panta,2)*pow(mid.x,2)-2*mid.x*mid.y*panta-2*mid.y*v[i].y+2*panta*mid.x*v[i].y+pow(v[i].y,2)-aux1+pow(v[i].x,2); //g<<"c="<<c<<" ";
         ec_gr2(a,b,c);
         test1.y=panta*test1.x+mid.y-panta*mid.x;
         test2.y=panta*test2.x+mid.y-panta*mid.x;

           }
         if(caut_bin(1,n,test1))
            nr++;
         if(caut_bin(1,n,test2))
            nr++;
       //  g<<test1.x<<"   "<<test1.y<<"       "<<test2.x<<"   "<<test2.y<<'\n'<<'\n';
      }
// g<<'\n';
 g<<nr/3;
 f.close();g.close();
}