Cod sursa(job #1090284)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 22 ianuarie 2014 15:48:32
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#define key 1009
using namespace std;
typedef struct {float xp,yp;int pozp;} PUNCT;
PUNCT pct[1001];
int per[1001];
vector <PUNCT> ha[key][key];
bool egale(float a, float b)
{
	if(fabs(a-b)<0.00001)
		return 1;
	return 0;
}
vector <PUNCT>::iterator 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(egale(it->xp,p.xp)&&egale(it->yp,p.yp))////////////////
			return it;
	return ha[lix][liy].end();
}
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;
	int p1,p2;
	PUNCT pn;
	vector <PUNCT>::iterator it;
	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++)
	{
		pct[i].pozp=i;
		inser(pct[i]);
	}
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
			//if(per[i]!=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;
					it=gaseste(pn);
					if(it!=ha[(int)pn.xp%key][(int)pn.yp%key].end())
					{
						p1=it->pozp;
						pn.xp=xm-dy;
						pn.yp=ym-dx;
						it=gaseste(pn);
						if(it!=ha[(int)pn.xp%key][(int)pn.yp%key].end())
						{
							p2=it->pozp;
							np++;
							per[p1]=p2;
							per[p2]=p1;
						}
					}
				}
				else
				{
					pn.xp=xm-dy;
					pn.yp=ym+dx;
					it=gaseste(pn);
					if(it!=ha[(int)pn.xp%key][(int)pn.yp%key].end())
					{
						p1=it->pozp;
						pn.xp=xm+dy;
						pn.yp=ym-dx;
						it=gaseste(pn);
						if(it!=ha[(int)pn.xp%key][(int)pn.yp%key].end())
						{
							p2=it->pozp;
							np++;
							per[p1]=p2;
							per[p2]=p1;
						}
					}
				}
			}
	freopen("patrate3.out","w",stdout);
	printf("%d\n",np);
	fclose(stdout);
	return 0;
}