Cod sursa(job #174840)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 9 aprilie 2008 12:07:55
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<fstream.h>

struct puncte {
	      long 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 (v[p].x<0 && v[u].x<0 || v[p].x>0 && v[u].x>0) {
									       if (v[p].y*v[u].x>v[p].x*v[u].y) return 1;
									       }
				else if (v[p].x==-1 || v[u].x==-1) if (v[p].y*v[u].x<v[u].y*v[p].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++)
			{
			v[++k].x=a[j].x-a[i].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 (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;
}