Cod sursa(job #174954)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 9 aprilie 2008 13:36:50
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<fstream.h>


struct puncte {
	      long long x,y;
	      };


int criteriu (puncte  v[499502],long p,long u)
	{
	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];v[0].x=v[0].y=0;
ifstream f("trapez.in");
f>>n;  long nr2=0,nr3=0;
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++)
			{
			v[++k].x=a[j].x-a[i].x;
			v[k].y=a[j].y-a[i].y;
			if (v[k].x==0) {nr2++; k--;};
			if (v[k].y==0)  {nr3++; k--;}
			}
quick(v,1,k);
i=1;long nr1=1; long nr=nr2*(nr2-1)/2+nr3*(nr3-1)/2;
while (i<k)
	{
	if (v[i].y*v[i+1].x==v[i].x*v[i+1].y) 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;
}