Cod sursa(job #286159)

Utilizator crawlerPuni Andrei Paul crawler Data 23 martie 2009 15:46:18
Problema Trapez Scor 0
Compilator cpp Status done
Runda qwerty-1 Marime 1.95 kb
#include <cstdio>
#include <math.h>

using namespace std;

#define Nmax 1024

int n, x[Nmax], y[Nmax], nr;
long long dx[Nmax*Nmax], dy[Nmax*Nmax];

int cmp(int i,int j)
{
     long long p1,p2;
     p1 = dy[i];
     p1 *= dx[j];     
     p2 = dy[j];
     p2 *= dx[i];
     if (p1 == p2) return 0;
     if (p1 < p2) return 1;
     return -1;     
}

void qsort(int st,int dr)
{
     int i=st,j=dr;
     long long tmp;
     dx[0] = dx[(i+j)/2];
     dy[0] = dy[(i+j)/2];
     do
     {
          while (cmp(i,0) == 1) ++i;
          while (cmp(j,0) == -1) --j;
          if (i<=j) 
          {
               tmp = dx[i];
               dx[i] = dx[j];
               dx[j] = tmp;
               tmp = dy[i];
               dy[i] = dy[j];
               dy[j] = tmp;
               ++i; --j;                    
          }     
     } while (i<=j);
     if (st<j) qsort(st,j);
     if (i<dr) qsort(i,dr);
}

int main()
{
     freopen("trapez.in","r",stdin);
     freopen("trapez.out","w",stdout);

     scanf("%d", &n);

     for (int i=1;i<=n;++i)
     {
          scanf("%d%d", x+i,y+i);
          for (int j=1;j<i;++j)
          {
               ++nr;
               dx[nr] = (long long)x[i];
               dx[nr] -=(long long)x[j];
               dy[nr] = (long long)y[i];
               dy[nr] -=(long long)y[j];   
          }               
     }
     
     qsort(1,nr);

     long long tmp = 0, ret = 0, a,b,c;
          
     for (int i=1;i<=nr;++i)
          if (cmp(i,i-1))
          {
               a = tmp;
               b = a-1;
               c = a;
               c *= b;
               c = c/2;
               if (c>0)
                    ret += c;
               tmp = 0;          
          }
               else
     ++tmp;
     a = tmp;
     b = a-1;
     c = a*b;
     c = c/2;
     if (c>0)
          ret += c;
               
     printf("%lld\n", ret);

     return 0;
}