Cod sursa(job #256934)

Utilizator otilia_sOtilia Stretcu otilia_s Data 12 februarie 2009 15:01:52
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define NMAX 1001
int n,nt,k;
typedef struct {int x,y;} punct;
punct P[NMAX],p1[NMAX*NMAX],p2[NMAX*NMAX];
float d[NMAX*NMAX];

void citire()
{ int i;
 FILE *fin=fopen("trapez.in","r");
 fscanf(fin,"%d",&n);
 for (i=1;i<=n;i++)
  fscanf(fin,"%d%d",&P[i].x,&P[i].y);
 fclose(fin);
}

float panta(punct a, punct b)
{
  if (a.x-b.x==0) return 0;
     else return (float) (a.y-b.y)/(a.x-b.x);
}

int pivot(int i, int j)
{int di,dj;
 di=1; dj=0;
 while (i<j)
  {
   if (d[i]>d[j]) { float aux=d[i]; d[i]=d[j]; d[j]=aux;
		    punct pct=p1[i]; p1[i]=p1[j]; p1[j]=pct;
		    pct=p2[i]; p2[i]=p2[j]; p2[j]=pct;
		    di^=1; dj^=1;
		  }
   i+=di;
   j-=dj;
  }
 return i;
}

void qsort(int st, int dr)
{
 if (st<dr) { int poz;
	     poz=pivot(st,dr);
	     qsort(st,poz-1);
	     qsort(poz+1,dr);
	    }
}

char coliniar(punct a, punct b,punct c)
{
 return (abs((c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x))<0.0000001);
}

char eg(float a, float b)
{
 return (fabs(a-b)<0.0000001);
}

void rez()
{ int i,j;
 k=0;
 for (i=1;i<n;i++)
  for (j=i+1;j<=n;j++)
   {
    d[++k]=panta(P[i],P[j]);
    p1[k]=P[i];
    p2[k]=P[j];
   }
 qsort(1,k);
 nt=0;
 for (i=1;i<k;i++)
  {
   j=i+1;
   while (eg(d[i],d[j]))
    {
     if (!coliniar(p1[i],p2[i],p1[j])) nt++;
     j++;
    }
  }
}

void afisare()
{
 FILE *fout=fopen("trapez.out","w");
 fprintf(fout,"%d\n",nt);
 fclose(fout);
}

int main()
{
 citire();
 rez();
 afisare();
 return 0;
}