Cod sursa(job #75172)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 30 iulie 2007 22:15:28
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
# include <stdio.h>
# include <math.h>

typedef struct PUNCT {double x,y;};
const long int MAXN=1500;
PUNCT pct[MAXN+1];
const double EPSILON=0.001;
long int n,sol;

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

double dist (PUNCT a, PUNCT b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double modul (double a) { if (a>=0) return a; return -a;}
double sign (double a) {if (a>=0) return 1; return -1;}

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

long int search(double x, double y)
{
long int li=1,lf=n,m;
while (li<=lf)
	{
	m=(li+lf)/2;
	if (modul(pct[m].x-x)<=EPSILON&&modul(pct[m].y-y)<=EPSILON) return 1;
	if ((pct[m].x-x)>EPSILON||(modul(pct[m].x-x)<=EPSILON&&(pct[m].y-y)>EPSILON)) lf=m-1;
	else li=m+1;
	}
return 0;
}

void calculeaza()
{
long int i,j;
PUNCT m,a,b;
double rad,l;
for (i=1;i<=n;i++)
	for (j=i+1;j<=n;j++)
		{
		m.x=(pct[i].x+pct[j].x)/2;
		m.y=(pct[i].y+pct[j].y)/2;
		a=pct[i];b=pct[j];
		l=dist(pct[i],pct[j]);
		rad=sqrt(3)/2;
		if (modul(a.x-b.x)<=EPSILON)
			{
			sol+=search(m.x-rad*l,m.y);
			sol+=search(m.x+rad*l,m.y);
			}
		else if (modul(a.y-b.y)<=EPSILON)
			{
			sol+=search(m.x,m.y+rad*l);
			sol+=search(m.x,m.y-rad*l);
			}
		else
			{
			if (sign(a.y-b.y)*sign(a.x-b.x)==1)
				{
				sol+=search(m.x-modul(b.y-a.y)*rad,m.y+modul(b.x-a.x)*rad);
				sol+=search(m.x+modul(b.y-a.y)*rad,m.y-modul(b.x-a.x)*rad);
				}
			else
				{
				sol+=search(m.x-modul(b.y-a.y)*rad,m.y-modul(b.x-a.x)*rad);
				sol+=search(m.x+modul(b.y-a.y)*rad,m.y+modul(b.x-a.x)*rad);
				}
			}
		}
}

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

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