Cod sursa(job #60411)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 14 mai 2007 09:06:55
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include<stdio.h>
struct panta{
long int a;
long int b;
int s;
};
int ord1(long int i1,long int i2);
int s1(long int i1,long int i2);
int hd1(long int ic,long int nc);
int ord2(long int i1,long int i2);
int s2(long int i1,long int i2);
int hd2(long int ic,long int nc);
int eq(long int i1,long int i2);
int auxi;
long int n,i,x[1001],y[1001],m,k,j,da,db,dd,dd1,poz,aux;
long long int cont,sol;
panta v[500501];
int main()
{
	FILE *f,*g;
	f=fopen("trapez.in","r");
	g=fopen("trapez.out","w");
	fscanf(f,"%ld",&n);
	for(i=1;i<=n;i++)
	fscanf(f,"%ld%ld",&x[i],&y[i]);
	for(i=n/2;i>=1;i--)
	hd1(i,n);
	for(i=n;i>=1;i--)
	{ s1(1,i);hd1(1,i-1);}
	m=(n*(n-1))/2;
	k=m;
	for(i=1;i<=n-1;i++)
	 for(j=i+1;j<=n;j++)
	  { da=x[j]-x[i];
	    if(da==0) {v[k].a=0;v[k].b=0;v[k].s=2;}
	    else { db=y[j]-y[i];
		   if(db==0) {v[k].a=0;v[k].b=0;v[k].s=0;}
		   else
		    { v[k].s=1;
		      if(db<0){ db=-db;v[k].s=-1;}
		      dd=da;dd1=db;while(dd1) {aux=dd1;dd1=dd%dd1;dd=aux;}
		      v[k].a=da/dd;
		      v[k].b=db/dd;
		    }
	    }
	     k--;
	 }
	 for(i=m/2;i>=1;i--)
	 hd2(i,m);
	 for(i=m;i>=1;i--)
	 { s2(1,i);hd2(1,i-1);}
	 poz=1;cont=1;
	 while(poz<m)
	 {
	    if(eq(poz,poz+1)){cont++;poz++;}
	    else { sol+=(cont*(cont-1))/2;cont=1;poz++;}
	 }
	 fprintf(g,"%lld",sol);
	 fcloseall();
	 return 0;
}

int ord1(long int i1,long int i2)
{
	if(x[i1]<x[i2]) return 1;
	return 0;
}
int s1(long int i1,long int i2)
{
	aux=x[i1];x[i1]=x[i2];x[i2]=aux;
	aux=y[i1];y[i1]=y[i2];y[i2]=aux;
	return 0;
}

int hd1(long int ic,long int nc)
{
	long int is=2*ic,is1=2*ic+1;
	if(is>nc) return 0;
	if(is<nc) if(ord1(is,is1)) is=is1;
	if(ord1(ic,is)) { s1(ic,is);hd1(is,nc);}
	return 0;
}
int ord2(long int i1,long int i2)
{
	if(v[i1].s<v[i2].s) return 1;
	if(v[i1].s>v[i2].s) return 0;
	if(v[i1].a<v[i2].a) return 1;
	if(v[i1].a>v[i2].a) return 0;
	if(v[i1].b<v[i2].b) return 1;
	if(v[i1].b>v[i2].b) return 0;
	return 0;
}
int s2(long int i1,long int i2)
{
	aux=v[i1].a;v[i1].a=v[i2].a;v[i2].a=aux;
	aux=v[i1].b;v[i1].b=v[i2].b;v[i2].b=aux;
	auxi=v[i1].s;v[i1].s=v[i2].s;v[i2].s=auxi;
	return 0;
}
int hd2(long int ic,long int nc)
{
	long int is=2*ic,is1=2*ic+1;
	if(is>nc) return 0;
	if(is<nc) if(ord2(is,is1)) is=is1;
	if(ord2(ic,is)) { s2(ic,is);hd1(is,nc);}
	return 0;
}

int eq(long int i1,long int i2)
{
	if(v[i1].a!=v[i2].a) return 0;
	if(v[i1].b!=v[i2].b) return 0;
	if(v[i1].s!=v[i2].s) return 0;
	return 1;
}