Cod sursa(job #43362)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 29 martie 2007 23:43:45
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define FIN "triang.in"
#define FOUT "triang.out"
#define MAX 2000
#define FOR(l,h,i) for(i=l;i<h;++i)
#define sqr(a) (a)*(a)
#define eps (float)0.0001
#define debug(x,y) printf("%lf %lf\n", x,y);
#define off 10005
#define tip float

struct point {
	tip x, y;
} A[MAX];

long n, nr;

int cmp(point A, point B) {
	return A.x<B.x || ( A.x==B.x && A.y<B.y ) ;
}

float abs(float x) {
	if ( x<0 ) 
		return -x;
	return x;
}

bool bs(float x, float y) {
	long st=0, dr=n-1;
	while ( st<=dr ) {
		long m = (st+dr)/2;
		if ( abs(A[m].x - x) < eps ) { // x e fixat
			if ( abs(A[m].y-y) < eps ) 
				return true;
			if ( A[m].y-y>eps )
				dr = m-1;
			if ( y-A[m].y>eps )
				st = m+1;
		}
		if ( A[m].x-x > eps )
			dr = m-1;
		if ( x-A[m].x > eps )
			st = m+1;
	}
	return false;
}

int main() {
	long i,j;

	freopen(FIN, "r", stdin);
	scanf("%ld", &n);
	FOR (0,n,i)
		scanf("%f %f", &A[i].x, &A[i].y);
	fclose(stdin);

	std::sort(A, A+i, cmp);

	float a,b,c, alpha, cp, xp, yp, kns = sqrt(3)/2, l;
	point m;

	FOR (0,n,i)
		FOR (i+1,n,j)
			if (i-j) {
				m.x = (A[i].x+A[j].x)/2, m.y= (A[i].y+A[j].y)/2 ;
				a = A[j].y-A[i].y;
				b = A[i].x-A[j].x;
				c = A[i].y*A[j].x-A[i].x*A[j].y;
				l = sqrt( sqr(A[i].x-A[j].x)+sqr(A[i].y-A[j].y) );
				alpha = l*kns*sqrt(a*a+b*b);
				cp = a*m.y-b*m.x;

				xp = (a*alpha-cp*b-a*c)/(a*a+b*b);
				if ( b ) 
					yp = (alpha-c-a*xp)/b;
				else
					yp = cp / a;
				// search
				if ( bs(xp, yp) ) 
					nr ++;

				alpha*=-1;
				xp = (a*alpha-cp*b-a*c)/(a*a+b*b);
				if ( b ) 
					yp = (alpha-c-a*xp)/b;
				else
					yp = cp / a;
				// search
				if ( bs(xp, yp) )
					nr ++;
			}

	freopen(FOUT, "w", stdout);
	printf("%ld\n", nr/3);
	fclose(stdout);
}