Cod sursa(job #323777)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 13 iunie 2009 14:32:27
Problema Trapez Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
#include<algorithm>
using namespace std;


struct nod
{ int x,y;

}a[1001];
 
long i,j,nr,n,k,afis,p;
int sor[1001000];
bool ok;

struct nod1
{ float m;
}rez[1001000]; 

bool fcomp( int i, int j)
{ 
  return rez[i].m<rez[j].m;
}

int main()
{ freopen("trapez.in","r",stdin);
  freopen("trapez.out","w",stdout);
  
   scanf("%d",&n);
   
   for(i=1;i<=n;i++) scanf("%d %d",&a[i].x,&a[i].y);
   for(i=1;i<=n;i++)
      for(j=i+1;j<=n;j++) { if(a[j].x-a[i].x==0) rez[++nr].m=0,p++;
      
                            else rez[++nr].m=(float)(a[j].y-a[i].y)/(a[j].x-a[i].x);
                            
                            sor[nr]=nr;
                          }
                            
  sort(sor+1,sor+nr+1,fcomp);
  afis=p*(p-1)/2;
  
  for(i=1;i<=nr;i++) { if(rez[sor[i]].m==0&&!ok) i=i+p,ok=1;
  
                       if(rez[sor[i]].m==rez[sor[i+1]].m) k++;
                       
                       else { afis+=k*(k+1)/2;
                              k=0;
                            }
                     }
  printf("%d\n",afis);
   fclose(stdin);
   fclose(stdout);
   return 0;
}