Cod sursa(job #286292)

Utilizator crawlerPuni Andrei Paul crawler Data 23 martie 2009 17:26:17
Problema Trapez Scor 40
Compilator cpp Status done
Runda qwerty-1 Marime 1.91 kb
#include <cstdio>
#include <math.h>

using namespace std;

#define Nmax 1024

int n, x[Nmax], y[Nmax], nr;
float p[Nmax*Nmax];

long long unu,doi;

float abs(float x)
{
     if (x>0)  return x;
     return -x;     
}

void qsort(int st,int dr)
{
     int i=st,j=dr;
     float tmp, sch = p[(i+j)/2];
     do
     {
          while (p[i] < sch) ++i;
          while (p[j] > sch) --j;
          if (i<=j) 
          {
               tmp = p[i];
               p[i] = p[j];
               p[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)
          {
              //if ((float)y[i]-(float)y[j] == 0) ++unu; else
              //if ((float)x[i]-(float)x[j] == 0) ++doi; else
              p[++nr] = (float)((float)y[i]-(float)y[j])/((float)x[i]-(float)x[j]+1e-23);
          }
     }
     
     qsort(1,nr);

     long long tmp = 1, ret = 0, a,b,c;
         
     for (int i=2;i<=nr;++i)
          if (abs(p[i]-p[i-1])>1e-20)
          {
               a = tmp;
               b = a-1;
               c = a;
               c *= b;
               c /= 2;
               if (c>0)
                    ret += c;
               tmp = 1;          
          }
               else
     ++tmp;
     
     a = tmp;
     b = a-1;
     c = a*b;
     c /= 2;
     if (c>0)
          ret += c;
          
     a = unu;
     b = a-1;
     c = a*b;
     c /= 2;
     if (c>0)
          ret += c;
     
     a = doi;
     b = a-1;
     c = a*b;
     c /= 2;
     if (c>0)
          ret += c;    
               
     printf("%lld\n", ret);

     return 0;
}