Cod sursa(job #461676)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 8 iunie 2010 09:19:40
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define double long double
typedef struct {long long x, y;char negativ;double dp;} panta;
typedef struct {long long x, y;} punct;
punct puncte[1000+1];
panta v[1000*1000+1];//N*N+1
long long n, contorTrapeze, dimv;
long long ndpx = -1;
void calculeazaPante()
{int i,j,indexPanta=0;
for(i=0;i<n;++i)
  {for(j=i+1;j<n;++j)
     {if(puncte[i].x==puncte[j].x)
       v[indexPanta].dp=-1234562;
      else
       v[indexPanta].dp=(double)((double)(puncte[i].y-puncte[j].y)/(double)(puncte[i].x-puncte[j].x));
      indexPanta++;}}
dimv=indexPanta;}
int fcmp(const void* a, const void* b)
{panta pa, pb;
pa=*((panta*)a);
pb=*((panta*)b);
if(pa.dp < pb.dp)
 return -1;
else
 return 1;}
void numaraTrapeze()
{int offset=0,depl;
while(offset<dimv-1)
  {depl=1;
  while(fabs(v[offset].dp-v[offset+depl].dp)<1E-14)
   depl++;
  contorTrapeze+=((depl-1)*depl/2);
  offset+=depl;}}
int main()
{freopen("trapez.in", "r", stdin);
freopen("trapez.out", "w", stdout);
scanf("%lld", &n);
int i;
for(i=0;i<n;++i)
 scanf("%lld%lld",&(puncte[i].x),&(puncte[i].y));
int j, indexPanta = 0;
for(i=0;i<n;++i)
  {for(j=i+1;j<n;++j)
     {if(puncte[i].x==puncte[j].x)
       v[indexPanta].dp=-1234562;
      else
       v[indexPanta].dp = (double)((double)(puncte[i].y - puncte[j].y) / (double)(puncte[i].x - puncte[j].x));
     indexPanta++;}}
dimv=indexPanta;
qsort(v, dimv, sizeof(panta), fcmp);
int offset = 0, depl;
while(offset < dimv - 1)
  {depl=1;
  while(fabs(v[offset].dp-v[offset+depl].dp)<1E-14)
   depl++;
  contorTrapeze+=((depl-1)*depl/2);
  offset += depl;}
printf("%lld\n", contorTrapeze);
return 0;}