Cod sursa(job #32671)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 18 martie 2007 12:26:49
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
# include <stdio.h>
# include <math.h>

typedef struct PUNCT {double x,y;};

const int MAXP=1500;

const double MARJA_EROARE=0.001;

PUNCT pct[MAXP+1];

long int sol;

int n;

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

void quick(int li, int lf)
{
int i=li,j=lf,ii=0,jj=-1,au;float aux;
while (i<j)
	{
	if (pct[i].x>pct[j].x||(pct[i].x==pct[j].x&&pct[i].y>pct[j].y))
		{
		aux=pct[i].x;pct[i].x=pct[j].x;pct[j].x=aux;
		aux=pct[i].y;pct[i].y=pct[j].y;pct[j].y=aux;
		au=ii;ii=-jj;jj=-au;
		}
	i+=ii;j+=jj;
	}
if (i-li>1) quick(li,i-1);
if (lf-i>1) quick(i+1,lf);
}

double modul(double a) {if (a<0) return -a; return a;}

int comp(PUNCT p, PUNCT a)
{
if (modul(p.x-a.x)<=MARJA_EROARE&&modul(p.y-a.y)<=MARJA_EROARE) return 0;
if (p.x-a.x>MARJA_EROARE || (p.x-a.x<=MARJA_EROARE&&p.y-a.y>MARJA_EROARE)) return 1;
return -1;
}

int search(PUNCT p)
{
int li=1,lf=n,m,au;
while (li<=lf)
	{
	m=(li+lf)/2;
	au=comp(p,pct[m]);
	if (au==0) return 1;
	if (au==-1) lf=m-1;
	if (au==1) li=m+1;
	}
return 0;
}

double dist(PUNCT a, PUNCT b)
{return sqrt( (a.y-b.y)*(a.y-b.y)+(a.x-b.x)*(a.x-b.x) );}

void panta_0(double d, PUNCT p)
{
PUNCT q=p;
q.y=p.y+d; sol+=search(q);
q.y=p.y-d; sol+=search(q);
}

void panta_infinit(double d, PUNCT p)
{
PUNCT q=p;
q.x=p.x+d; sol+=search(q);
q.x=p.x-d; sol+=search(q);
}

void panta_m(double m, double d, PUNCT p)
{
PUNCT q;
m=-1/m;
double rad=d/sqrt(m*m+1);
q.x=rad+p.x;
q.y=m*rad+p.y;
sol+=search(q);
q.x=p.x-d/sqrt(m*m+1);
q.y=-d*m/sqrt(m*m+1)+p.y;
sol+=search(q);
}

void determine()
{
int i,j;
PUNCT p;
double m,d;
for (i=1;i<=n;i++)
	for (j=i+1;j<=n;j++)
		{
		//determinam puctele si unde ar trebui sa se afle ele
		d=dist(pct[i],pct[j]);
		d=d*sqrt(3)/2;
		//d
		p.x=(pct[i].x+pct[j].x)/2;
		p.y=(pct[i].y+pct[j].y)/2;
		//xp, yp

		//PANTA
		if (pct[i].x==pct[j].x) panta_infinit(d,p);
		else if (pct[i].y==pct[j].y) panta_0(d,p);
		else
			{
			m=(pct[j].y-pct[i].y)/(pct[j].x-pct[i].x);
			panta_m(m,d,p); 
			}
		}
}

void scrie()
{
FILE *g=fopen("triang.out","w");
fprintf(g,"%ld\n",sol/3);
fcloseall();
}

int main()
{
citire();
quick(1,n);
determine();
scrie();
return 0;
}