Cod sursa(job #174812)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 9 aprilie 2008 11:53:05
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<fstream.h>

struct puncte {
	      long x,y;
	      };


int criteriu (puncte v[499502],long p,long u)
	{
	if (v[p].x==0) return 0;
		else if (v[u].x==0) return 1;
			else if ((double)v[p].y/v[p].x>(double)v[u].y/v[u].x) return 1;
	return 0;
	}

long poz (puncte v[499502], long p,long u)
	{
	puncte aux,piv=v[p];
	while (p<u)
		{
		if (criteriu(v,p,u)==1) {
		      aux=v[p];
		      v[p]=v[u];
		      v[u]=aux;
		      }
		if (piv.x==v[p].x && piv.y==v[p].y) u--;
			else p++;
		}
	return p;
	}

void quick (puncte v[499502], long a, long b)
	{
	long k;
	if (a<b) {
		 k=poz (v,a,b);
		 quick(v,a,k);
		 quick(v,k+1,b);
		 }
	}

int main()
{
int n,i,j;
long k=0;
puncte a[1002],v[499502];
ifstream f("trapez.in");
f>>n;
for (i=1;i<=n;i++) f>>a[i].x>>a[i].y;f.close();
for (i=1;i<n;i++)
	for (j=i+1;j<=n;j++)
			if (a[i].x<a[j].x) {
				   v[++k].x=a[j].x-a[i].x;
				   v[k].y=a[i].y-a[j].y;
				   }
			      else {
				   v[++k].x=a[i].x-a[j].x;
				   v[k].y=a[j].y-a[i].y;
				   }
quick(v,1,k);
i=1; long nr=1,nr1=0;
while (v[i].x==0 && i<=n)
	{
	nr1++;
	i++;
	}
nr+=(nr1*(nr1-1)/2);nr1=1;
while (i<n)
	{
	if ((double)v[i].y/v[i].x==(double)v[i+1].y/v[i+1].x) nr1++;
		else {
		     nr+=nr1*(nr1-1)/2;
		     nr1=1;
		     }
	i++;
	}
if (nr1>1) nr+=nr1*(nr1-1)/2;
ofstream g("trapez.out");
g<<nr;  g.close();
return 0;
}