Cod sursa(job #68388)

Utilizator vmaneavmanea vmanea Data 27 iunie 2007 19:02:53
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.01 kb
#include <stdio.h>

#define nmax 1005

//int V[nmax];
double a, b;
long X[nmax], Y[nmax], XX[nmax], YY[nmax];
long XXX[nmax], YYY[nmax];
long IX[nmax], IY[nmax], IXX[nmax], IYY[nmax];
long i, j, k, ix3, ix4, N, k3, k4, A, B;
long x1, y1, x2, y2, x3, y3, x4, y4;
long long patrate;



int bsx(float v, int l, int r)
{
	if (l > r) return 0;

	int m = (l + r) >> 1;

	if (XX[m] > v)
		return bsx(v, l, m-1);
	else if (XX[m] < v)
		return bsx(v, m+1, r);

	return m;
}

void msortX(int l, int r)
{
	if (l >= r)
		return;

	int m = (l+r) >> 1;

	msortX(l, m);

	msortX(m+1, r);

	for (i = k = l, j = m+1; i <= m && j <= r;)
		if (XX[i] < XX[j])
		{
			XXX[k] = XX[i];
			IXX[k++] = IX[i++];
		}
		else
		{
			XXX[k] = XX[j];
			IXX[k++] = IX[j++];
		}

	while (i <= m)
	{
		XXX[k] = XX[i];
		IXX[k++] = IX[i++];
	}

	while (j <= r)
	{
		XXX[k] = XX[j];
		IXX[k++] = IX[j++];
	}

	for (i = l; i <= r; i++)
	{
		XX[i] = XXX[i];
		IX[i] = IXX[i];
	}
}

void msortY(int l, int r)
{
	if (l >= r)
		return;

	int m = (l+r) >> 1;

	msortY(l, m);

	msortY(m+1, r);

	for (i = k = l, j = m+1; i <= m && j <= r;)
		if (YY[i] < YY[j])
		{
			YYY[k] = YY[i];
			IYY[k++] = IY[i++];
		}
		else
		{
			YYY[k] = YY[j];
			IYY[k++] = IY[j++];
		}

	while (i <= m)
	{
		YYY[k] = YY[i];
		IYY[k++] = IY[i++];
	}

	while (j <= r)
	{
		YYY[k] = YY[j];
		IYY[k++] = IY[j++];
	}

	for (i = l; i <= r; i++)
	{
		YY[i] = YYY[i];
		IY[i] = IYY[i];
	}
}

int main(void)
{
	freopen("patrate3.in", "r", stdin);
	freopen("patrate3.out", "w", stdout);

	scanf("%d", &N);

	for (i = 1; i <= N; i++)
	{
		scanf("%lf%lf", &a, &b);

		A = a * 10000;
		B = b * 10000;

		if (A % 10)
		{
		  if ((A + 1) % 10 == 0)
			A++;
		  else
			A--;
		}

		if (B % 10)
		{
		  if ((B + 1) % 10 == 0)
			B++;
		  else
			B--;
		}

		XX[i] = X[i] = A; // voi sorta in vectorul xx
		YY[i] = Y[i] = B; // voi sorta in vectorul yy

		IX[i] = IY[i] = i; // voi retine in ix[i] cine a fost inainte
	}

	msortX(1, N);

	msortY(1, N);

	for (i = 1; i <= N; i++)
	 for (j = 1 + i; j <= N; j++)
	 {
	   x1 = X[i];
	   y1 = Y[i];

	   x2 = X[j];
	   y2 = Y[j];

	   x3 = x1 + y1 - y2;
	   y3 = y1 + x2 - x1;

	   x4 = x3 + x2 - x1;
	   y4 = y3 + y2 - y1;

	   ix3 = bsx(x3, 1, N);

	   if (ix3)
	   {
	     k3 = k4 = 0;

	     for (k = ix3; k >= 1 && !k3 && XX[k] == x3; k--)
	       if (y3 == Y[IX[k]] && IX[k] != i && IX[k] != j)
		 k3 = IX[k];

	     for (k = ix3; k <= N && !k3 && XX[k] == x3; k++)
	       if (y3 == Y[IX[k]] && IX[k] != i && IX[k] != j)
		 k3 = IX[k];

	     if (k3) // am al treilea punct
	     {
	       ix4 = bsx(x4, 1, N);

	       if (ix4)
	       {
		 for (k = ix4; k >= 1 && !k4 && XX[k] == x4; k--)
		   if (y4 == Y[IX[k]] && IX[k] != i && IX[k] != j && IX[k] != k3)
		     k4 = IX[k];

		 for (k = ix4; k <= N && !k4 && XX[k] == x4; k++)
		   if (y4 == Y[IX[k]] && IX[k] != i && IX[k] != j && IX[k] != k3)
		     k4 = IX[k];

		 if (k4)
			patrate++;
	       }
	     }
	   }

	   x3 = x1 + y2 - y1;
	   y3 = y1 + x1 - x2;

	   x4 = x3 + x2 - x1;
	   y4 = y3 + y2 - y1;

	   ix3 = bsx(x3, 1, N);

	   if (ix3)
	   {
	     k3 = k4 = 0;

	     for (k = ix3; k >= 1 && !k3 && XX[k] == x3; k--)
	       if (y3 == Y[IX[k]] && IX[k] != i && IX[k] != j)
		 k3 = IX[k];

	     for (k = ix3; k <= N && !k3 && XX[k] == x3; k++)
	       if (y3 == Y[IX[k]] && IX[k] != i && IX[k] != j)
		 k3 = IX[k];

	     if (k3) // am al treilea punct
	     {
	       ix4 = bsx(x4, 1, N);

	       if (ix4)
	       {
		 for (k = ix4; k >= 1 && !k4 && XX[k] == x4; k--)
		   if (y4 == Y[IX[k]] && IX[k] != i && IX[k] != j && IX[k] != k3)
		     k4 = IX[k];

		 for (k = ix4; k <= N && !k4 && XX[k] == x4; k++)
		   if (y4 == Y[IX[k]] && IX[k] != i && IX[k] != j && IX[k] != k3)
		     k4 = IX[k];

		 if (k4)
			patrate++;
	       }
	     }
	   }

	 }

       printf("%Ld\n", patrate >> 2);

       return 0;
}