Cod sursa(job #97810)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 8 noiembrie 2007 22:23:04
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <stdio.h>
#include <stdlib.h>
#include <fstream.h>

int contor, n, ord[1000];

typedef struct
{
	float x, y;
} punct;
punct a[1000], b[1000];

int cmp(const void *a, const void *c)
{
   int x=*(int *)a, y=*(int *)c;
   if (b[x].x == b[y].x) return b[x].y-b[y].y;
   else return b[x].x-b[y].x;
}

void citire()
{
	ifstream in("patrate3.in");
	freopen("patrate3.out","w",stdout);

	in>>n;
	int i;
	for (i=1; i<=n; i++)
	{
		in>>b[i].x>>b[i].y;
		ord[i]=i;
	}
}

int caut(long x, long y, int p, int u)
{
	int m;
	long xx, yy;
	m=(p+u)/2;
	while (p<=u)
	{
		xx = (long) a[m].x*10000;
		yy = (long) a[m].y*10000;
		if (xx==x && yy==y) return 1;
		else if ((xx==x && yy<y) || (xx<x)) {p=m+1; m=(p+u)/2;}
		else if ((xx==x && yy>y) || (xx>x)) {u=m-1; m=(p+u)/2;}
	}
	return 0;
}

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

int main()
{
	citire();
	int i, j;

	qsort(ord,n+1,sizeof(int),cmp);
	for (i=1; i<=n; i++) a[i]=b[ord[i]];

	float mijx, mijy, dx, dy;
	long x3, y3, x4, y4;
	
	for (i=1; i<=n; i++)
		for (j=i+1; j<=n; j++)
		{
			mijx = (float) (a[i].x+a[j].x)/2;
			mijy = (float) (a[i].y+a[j].y)/2;
			
			dx = ab(mijx - a[i].x);
			dy = ab(mijy - a[i].y);

			if (a[i].y < a[j].y)
			{
				x3 = (long)(mijx + dy)* 10000; 
				y3 = (long)(mijy - dx)* 10000;
				x4 = (long)(mijx - dy)* 10000;
				y4 = (long)(mijy + dx)* 10000;
			}
			else
			{
				x3 = (long)(mijx - dy)* 10000; 
				y3 = (long)(mijy - dx)* 10000;
				x4 = (long)(mijx + dy)* 10000;
				y4 = (long)(mijy + dx)* 10000;
			}

			if (caut(x3, y3, 1, n) && caut(x4, y4, 1, n)) contor++;
		}
	printf("%d\n",contor/2);
	return 0;
}