Cod sursa(job #357932)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 21 octombrie 2009 11:34:59
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 1<<11
#define aprox 0.0001
int n,rez;
double a,b,c;
struct coord
{
	double x,y;
};
coord v[N];
double dist_pcte(coord a,coord b)
{
	return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int egal(double a,double b)
{
	if (a-b>=(aprox*-1) &&  a-b<=aprox)
		return 1;
	return 0;
}
int compar(const void *p,const void *q)
{
	coord r=*(coord*)p;
	coord s=*(coord*)q;
	if (r.x-s.x<aprox)
		return -1;
	if (r.x-s.x>aprox)
		return 1;
	if (r.y-s.y<aprox)
		return -1;
	if (r.y-s.y>aprox)
		return 1;
	return 0;
}
int cbin(double x1,double y1)
{
	int i,j,step;
	for (step=1 ; step <=n; step<<=1);
	for (i=0; step; step>>=1)
		if (i+step<=n && v[i+step].x-x1<-aprox)
			i+=step;
	i++;
	if (!egal(v[i].x,x1))
		return -1;
	for (j=i; j<=n && egal(v[j].x,x1); j++)
		if (egal(v[j].y,y1))
			return j;
	return -1;
}
int main()
{
	freopen("triang.in","r",stdin);
	freopen("triang.out","w",stdout);
	scanf("%d",&n);
	int i,j,k,poz;
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&v[i].x,&v[i].y);
	qsort(v+1,n,sizeof(v[0]),compar);
	double val,a,b,c,val2,val3,val4,y1,y2,x1,x2,delta;
	for (i=1; i<=n-1; i++)
		for (j=i+1; j<=n; j++)
		{
			val=dist_pcte(v[i],v[j]);
			val2=2*(v[j].x-v[i].x)*(v[j].x-v[i].x)*(v[i].y-v[j].y);
			val3=(v[j].x-v[i].x)*(v[j].x-v[i].x);
			val3=val3*val3;
			val4=(v[i].y-v[j].y)*(v[i].y-v[j].y);
			a=4*(v[i].y-v[j].y)*(v[i].y-v[j].y)+4*(v[j].x-v[i].x)*(v[j].x-v[i].x);
			b=-4*v[i].y*val4-4*v[j].y*val4+2*val2-8*v[i].y*(v[j].x-v[i].x)*(v[j].x-v[i].x);
			c=val4*v[i].y*v[i].y+val4*v[j].y*v[j].y+2*val4*v[i].y*v[j].y+val3+val2*(-v[i].y-v[j].y)+
			  v[i].y*v[i].y*4*(v[j].x-v[i].x)*(v[j].x-v[i].x)-val*4*(v[j].x-v[i].x)*(v[j].x-v[i].x);
			delta=b*b-4*a*c;
			delta=sqrt(delta);
			y1=(-b+delta)/(2*a);
			y2=(-b-delta)/(2*a);
			x1=(v[i].x+v[j].x)/2+(1/(2*(v[j].x-v[i].x)))*(v[i].y-v[j].y)*(2*y1-v[i].y-v[j].y);
			x2=(v[i].x+v[j].x)/2+(1/(2*(v[j].x-v[i].x)))*(v[i].y-v[j].y)*(2*y2-v[i].y-v[j].y);
			poz=cbin(x1,y1);
			if (poz!=-1 && poz>j)
				rez++;
			poz=cbin(x2,y2);
			if (poz!=-1 && poz>j)
				rez++;
		}
	printf("%d\n",rez);
	return 0;
}