Cod sursa(job #1044828)

Utilizator Dayanna000Amegica Dayanna Dayanna000 Data 30 noiembrie 2013 15:06:07
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;
double a[500601];
void quicksort(double a[],long st,long dr)
  {
      long i,j;
      double aux,x,y,z,piv,mi,ma;
      i=st;
      j=dr;
      x=a[rand()%(j-i+1)+i];
      y=a[rand()%(j-i+1)+i];
      z=a[rand()%(j-i+1)+i];
       if(x<=y && x<=z)
          mi=x;
       if(y<=x && y<=z)
          mi=y;
       if(z<=x && z<=y)
          mi=z;
       if(x>=y && x>=z)
          ma=x;
       if(y>=x && y>=z)
          ma=y;
       if(z>=x && z>=y)
          ma=z;
      piv=x+y+z-mi-ma;
      while (i <= j)
         {

        while (a[i]<piv)
            i++;
        while (a[j]>piv)
           j--;
        if (i <= j)
              {
                aux = a[i];
                a[i] = a[j];
                a[j] = aux;
                i++;
                j--;
              }
        }

    if (st < j)
       quicksort(a,st,j);
    if (i < dr)
        quicksort(a,i,dr);
}

int main()
{
    ifstream f("trapez.in");
    ofstream g("trapez.out");
    long n,i,j,nr=0,c[1001],d[1001],s,suma;
    f>>n;
    for(i=1;i<=n;i++)
        f>>c[i]>>d[i];
    for(i=1;i<=n-1;i++)
         for(j=i+1;j<=n;j++)
            if(c[i]==c[j])
               {
                   nr++;
                   a[nr]=1000000006;
               }
               else
               {
                   nr++;
                   a[nr]=(float)(d[j]-d[i])/(c[j]-c[i]);
               }

    quicksort(a,1,nr);
    s=0;
    suma=0;
    for(i=1;i<=nr-1;i++)
      if(a[i]==a[i+1])
          s++;
          else
          {
              suma=suma+s*(s-1)/2;
              s=1;
          }
    suma=suma+s*(s-1)/2;
    g<<suma;
    f.close();
    g.close();
    return 0;
  }