Cod sursa(job #783645)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 3 septembrie 2012 15:07:25
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#define N 1005
using namespace std;
long long x[N],y[N],a[N*N],b[N*N];
unsigned long long sol;
int k,n;
void qsort(int l,int r)
{ int i,j;
  long long mija,mijb,z;
i=l; j=r; mija=a[(i+j)/2]; mijb=b[(i+j)/2];
do
{
while(a[i]*mijb<b[i]*mija)++i;
while(mija*b[j]<mijb*a[j])--j;
if(i<=j)
    {
    z=a[i]; a[i]=a[j]; a[j]=z;
    z=b[i]; b[i]=b[j]; b[j]=z;
    ++i; --j;
    }
}
while(i<=j);
if(i<r)qsort(i,r);
if(l<j)qsort(l,j);
}
int main()
{ int i,j;
  unsigned long long d;
  ifstream f("trapez.in"); f>>n;
k=0;
for(i=1;i<=n;++i)
    {
    f>>x[i]>>y[i];
    for(j=i-1;j>=1;--j)
        {
        ++k; a[k]=y[i]-y[j]; b[k]=x[i]-x[j];
        }
    }
f.close();
qsort(1,k);
i=1; sol=0;
while(i<=k)
    {
    j=i; d=0;
    while(a[j]*b[j+1]==b[j]*a[j+1]&&j<k)
        {
        ++d; ++j;
        }
    sol=sol+d*(d+1)/2;
    i=j+1;
    }
ofstream g("trapez.out"); g<<sol; g.close();
return 0;

}
#undef N