Cod sursa(job #43367)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 29 martie 2007 23:49:24
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 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 (tip)0.0001
#define debug(x,y) printf("%lf %lf\n", x,y);
#define off 10005
#define tip double

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 ) ;
}

inline tip abs(tip x) {
	return ( x<0 ) ? -x : x;
}

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

int main() {
	long i,j;

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

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

	tip a,b,c, alpha, cp, xp, yp, kns = sqrt(3)/2, l;
	tip pp;
	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) );
				pp = sqr(a)+sqr(b);
				alpha = l*kns*sqrt(pp);
				cp = a*m.y-b*m.x;

				xp = (a*alpha-cp*b-a*c)/(pp);
				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)/(pp);
				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);
}