Cod sursa(job #43255)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 29 martie 2007 22:31:25
Problema Triang Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define FIN "triang.in"
#define FOUT "triang.out"
#define MAX 1500
#define FOR(l,h,i) for(i=l;i<h;++i)
#define sqr(a) (a)*(a)
#define eps (double)0.0001
#define debug(x,y) printf("%lf %lf\n", x,y);

struct point {
	double x, y;
} A[MAX];
/*point* H[20080];
#define H (H+10000)*/

long n, nr;

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

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

bool bs(double x, double y) {
	long st = 0, dr = n;
	while ( st<=dr ) {
		long m = (st+dr)/2;
		if ( abs(A[m].x - x) < eps ) { // x e fixat
//          	printf("%.20lf\n", (double)abs(A[m].y-y));
			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("%lf %lf", &A[i].x, &A[i].y);
	fclose(stdin);

	std::sort(A, A+i, cmp);
/*	FOR (0,n,i)
		if ( !H[(long)floor(A[i].x)] ) 
			H[(long)floor(A[i].x)] = A+i;*/

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

	FOR (0,n,i)
		FOR (i+1,n,j)
			if (i-j) {
				point m = { (A[i].x+A[j].x)/2, (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);
}