Cod sursa(job #583012)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 17 aprilie 2011 12:03:28
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<stdio.h>
#define N 1001
#define M 1000001
long a[N],b[N],l=0,t=0,p=0,r=0,q=0,i,j;
long long c[M],d[M],x[M],y[M];
int n;
void merge(long long c[M],long long d[M],long p,long q)
{long m=(p+q)>>1,i,j,k;
if(p==q)
       return;
merge(c,d,p,m);
merge(c,d,m+1,q);
for(i=p,j=m+1,k=p;i<=m||j<=q;)
if(j>q||(i<=m&&(c[i]*d[j]<c[j]*d[i]||(c[i]*d[j]==c[j]*d[i]&&(c[i]<c[j]||(d[i]<d[j]&&c[i]==c[j]))))))
       {x[k]=c[i];
       y[k]=d[i];
       k++;
       i++;}
else
       {x[k]=c[j];
       y[k]=d[j];
       k++;
       j++;}
for(i=p;i<=q;i++)
       {c[i]=x[i];
       d[i]=y[i];}}

int main()
{freopen("trapez.in","r",stdin);
freopen("trapez.out","w",stdout);
scanf("%d\n",&n);
for(i=1;i<=n;i++)
      scanf("%ld%ld\n",&a[i],&b[i]);
for(i=1;i<n;i++)
      {for(j=i+1;j<=n;j++)
              {if(b[j]==b[i])
                      p++;
              if(a[j]==a[i])
                      r++;
              if(b[j]!=b[i]&&a[j]!=a[i])
                      {l++;
                      c[l]=b[j]-b[i];
                      d[l]=a[j]-a[i];}}}
for(i=1;i<=l;i++)
if(d[i]<0)
      {c[i]=-c[i];
      d[i]=-d[i];}
merge(c,d,1,l);
for(i=1;i<l;i++)
if(c[i]*d[i+1]==c[i+1]*d[i])
      t++;
else
      {q=q+t*(t+1)/2;
      t=0;}
if(t>0)
      q=q+t*(t+1)/2;
printf("%ld\n",q+p*(p-1)/2+r*(r-1)/2);
fclose(stdin);
fclose(stdout);
return 0;}