Cod sursa(job #1090266)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 22 ianuarie 2014 15:27:50
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#define key 1009
using namespace std;
typedef struct {float xp,yp;} PUNCT;
PUNCT pct[1001];
vector <PUNCT> ha[key][key];
bool gaseste(PUNCT p)
{
	int lix,liy;
	lix=(int)p.xp%key;
	liy=(int)p.yp%key;
	vector <PUNCT>::iterator it;
	for(it=ha[lix][liy].begin();it!=ha[lix][liy].end();it++)
		if((it->xp==p.xp)&&(it->yp==p.yp))////////////////
			return 1;
	return 0;
}
void inser(PUNCT p)
{
	ha[(int)p.xp%key][(int)p.yp%key].push_back(p);
}
bool compPUNCT(PUNCT a, PUNCT b)
{
	if(a.xp<b.xp)
		return 1;
	if((a.xp==b.xp)&&(a.yp<b.yp))
		return 1;
	return 0;
}
int main()
{
	int n;
	int np=0;
	int i,j;
	float xm,ym,dx,dy;
	PUNCT pn;
	freopen("patrate3.in","r",stdin);
	scanf("%d\n",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%f %f\n",&pct[i].xp,&pct[i].yp);
		pct[i].xp+=10000.0;
		pct[i].yp+=10000.0;
		inser(pct[i]);
	}
	fclose(stdin);
	sort(pct+1, pct+n+1, compPUNCT);
	for(i=1;i<n;i++)
		for(j=1;j<=n;j++)
		{
			xm=(pct[i].xp+pct[j].xp)/2;
			ym=(pct[i].yp+pct[j].yp)/2;
			dx=fabs(pct[i].xp-xm);
			dy=fabs(pct[i].yp-ym);
			if(pct[i].yp>pct[j].yp)
			{
				pn.xp=xm+dy;
				pn.yp=ym+dx;
				if(gaseste(pn))
				{
					pn.xp=xm-dy;
					pn.yp=ym-dx;
					if(gaseste(pn))
						np++;
				}
			}
			else
			{
				pn.xp=xm-dy;
				pn.yp=ym+dx;
				if(gaseste(pn))
				{
					pn.xp=xm+dy;
					pn.yp=ym-dx;
					if(gaseste(pn))
						np++;
				}
			}
		}
	freopen("patrate3.out","w",stdout);
	printf("%d\n",np);
	fclose(stdout);
	return 0;
}