Cod sursa(job #286143)

Utilizator crawlerPuni Andrei Paul crawler Data 23 martie 2009 15:32:32
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 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]*dx[j];
     p2 = dy[j]*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(0,j) == 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]-(long long)x[j];
               dy[nr] = (long long)y[i]-(long long)y[j];   
          }               
     }

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

     return 0;
}