Cod sursa(job #16648)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 13 februarie 2007 20:28:05
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
# include <stdio.h>

# define  _fin  "patrate3.in"
# define  _fout "patrate3.out"

# define  maxn  1002

# define  eps   0.0001


double cx[maxn], cy[maxn];
int n, sol;


void readf()
{
	freopen(_fin, "r", stdin);
	int i;
	float auxx, auxy;
	
	for (scanf("%d", &n), i=1; i<=n; i++)
		 scanf("%f %f", &auxx, &auxy),
		 cx[i] = auxx, cy[i] = auxy;
}

int qspoz(int st, int dr)
{
	double xx=cx[st], xy=cy[st];
	
	while ( st < dr )
	{
		while ( st < dr && ( cx[dr] > xx || ( cx[dr]==xx && cy[dr]>=xy ) ) ) dr--;
		cx[st] = cx[dr], cy[st] = cy[dr];
		while ( st < dr && ( cx[st] < xx || ( cx[st]==xx && cy[st]<=xy ) ) ) st++;
		cx[dr] = cx[st], cy[dr] = cy[st];
	}
	cx[st]=xx, cy[st]=xy;
	return st;
}

void qs(int st, int dr)
{
	int m = qspoz(st, dr);
	if ( st < m ) qs(st, m-1);
	if ( m < dr ) qs(m+1, dr);
}

inline int smaller(double x1, double x2) { return x2-x1 >= eps; }
inline double abs    (double x) { return x>0?x:-x; }
inline int equal  (double x1, double x2) { return abs(x1-x2) <= eps; }

int bsearch(double x, double y)
{
	int i, step;
	for (step=1; step<=n; step<<=1); step>>=1;
	for (i=1; step; step>>=1)
		if ( i+step <= n )
			if ( smaller(cx[i+step], x) || ( equal(cx[i+step], x) && ( cy[i+step] <= y || equal (cy[i+step], y) ) ) )
				i+=step;
				
	return ( equal(cx[i], x) && equal(cy[i], y) );
}

void solve()
{
/*mijx = (x0 + x1) / 2 si mijy = (y0 + y1) / 2. Sa notam dx = abs(mijx - x0) si dy = abs(mijy - y0). 
Se observa ca daca y0 < y1 atunci x2 = mijx + dy, y2 = mijy - dx, x3 = mijx - dy iar y3 = mijy + dx. 
In caz contrar, avem x2 = mijx - dy, y2 = mijy - dx, x3 = mijx + dy iar y3 = mijy + dx.*/
	double x3, y3, x4, y4, mx, my, dx, dy;
	int i, j;

	qs(1, n);

	for (i=1; i<n; i++)
		for (j=i+1; j<=n; j++)
		{
			mx = ( cx[i]+cx[j] ) / 2,
			my = ( cy[i]+cy[j] ) / 2;
			dx = abs( mx-cx[i] );
			dy = abs( my-cy[i] );
			
			if ( cy[i] < cy[j] )
			{
				x3 = mx + dy;
				y3 = my - dx;
				x4 = mx - dy;
				y4 = my + dx;
			}
			else
			{
				x3 = mx - dy;
				y3 = my - dx;
				x4 = mx + dy;
				y4 = my + dx;
			}
			
			sol += ( bsearch(x3, y3) && bsearch(x4, y4) );
		}
	sol /= 2;
}

void writef()
{
	freopen(_fout, "w", stdout);
	printf("%d\n", sol);
}

int main()
{
	readf();
	solve();
	writef();

	return 0;
}