Cod sursa(job #1022)

Utilizator mika17Mihai Alex Ionescu mika17 Data 12 decembrie 2006 14:08:10
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ERR(d) fprintf(stderr,d)
#define Err(f,d) fprintf(stderr,f,d)
#define For(i,a,n) for(int i=(a);i<(n);++i)
#define abs(x) ((x)<0?-(x):(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define FOR(i,n) for(int i=0;i<(n);++i)
#define ROF(i,n) for(int i=(n);i>=0;--i)
#define DIF 0.00000000000001
#define MAX 1001
typedef long long int64;
typedef unsigned pint;

double a[500*999];
int n,x[MAX],y[MAX];
void citire(void) {
freopen("trapez.in","rt",stdin);
freopen("trapez.out","wt",stdout);
scanf("%d",&n);
for(int i=0;i<n;++i)
 scanf("%d %d",x+i,y+i);
fclose(stdin);
//for(int i=0;i<n;++i)
//   fprintf(stderr,"%d %d\n",x[i],y[i]);
}

void qsort(int st,int dr) {
double x=a[(st+dr)/2];
int i=st,j=dr;
while(i<=j)
  {
   while(a[j]>x) --j;
   while(a[i]<x) ++i;
   if(i<=j)
     {
     double y=a[i]; a[i]=a[j]; a[j]=y;
     ++i; --j;
     }
  }
if(i<dr) qsort(i,dr);
if(st<j) qsort(st,j);
}

bool equal(double x,double y)
{
 if(abs(x-y)<0.00000000000001)
   return true;
  return false;
}

int solve(void) {
int oriz=0,vert=0,k=0,numb=0,nr=1;
for(int i=0;i<n;++i)
   for(int j=i+1;j<n;++j)
     if(x[j]==x[i]) ++vert;
      else if(y[j]==y[i]) ++oriz;
         else a[k++]=double(y[j]-y[i])/(x[j]-x[i]);
qsort(0,k-1);
//for(int i=0;i<k;++i)
//   fprintf(stderr,"%.21f ",a[i]);
for(int i=1;i<k;++i)
   if(equal(a[i],a[i-1])) nr++;
    else {
          numb+=nr*(nr-1)/2;
          nr=1;
         }
   if(nr>1) numb+=nr*(nr-1)/2;
return (oriz)*(oriz-1)/2+(vert)*(vert-1)/2+numb;
}

int main(void) {
citire();
printf("%d",solve());
return 0;
}