Cod sursa(job #1017643)

Utilizator Iustin_BulimarFMI Iustin Bulimar Iustin_Bulimar Data 28 octombrie 2013 01:12:16
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>

using namespace std;

ifstream cin("trapez.in");
ofstream cout("trapez.out");

short n, i, j;
int k, t, a, b, v, r;
float x[1001], y[1001], p[600001];
void qsort(float v[], int st, int dr)
{
      int i=st, j=dr;
      float piv = v[(st+dr)/2];
      while (i <= j)
      {
            while (v[i] < piv) i++;
            while (v[j] > piv) j--;
            if (i <= j)
            {
                  swap(v[i],v[j]);
                  i++;
                  j--;
            }
      }
      if (st < j) qsort(v, st, j);
      if (i < dr) qsort(v, i, dr);
}
int main()
{
    cin>>n;
    for(i=1; i<=n; i++) cin>>x[i]>>y[i];
    for(i=1; i<n; i++)
        for(j=i+1; j<=n; j++)
        {
            ++k;
            if(y[i]-y[j]==0) k--, a++;
            else
                if(x[i]-x[j]==0) k--, b++;
                else p[k]=(y[i]-y[j])/(x[i]-x[j]);
        }
    t+=a*(a-1)/2+b*(b-1)/2;
    qsort(p, 1, k);
    i=1;
    while(i<=k)
    {
        v=p[i];
        i++;
        r=1;
        while(p[i]==v)
        {
            i++;
            r++;
        }
        t+=r*(r-1)/2;
    }
    cout<<t;
    return 0;
}