Cod sursa(job #655559)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 2 ianuarie 2012 20:50:17
Problema Patrate 3 Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include<fstream>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#define NMAX 1001

using namespace std;

ifstream f("patrate3.in");
ofstream g("patrate3.out");

struct st
{
	int x, y;
}a[NMAX];
int n, nr;


void Citeste()
{
	int i;
	double x, y;
	f>>n;
	for (i=1; i<=n; ++i)
	{
		f>>x>>y;
		a[i].x=x*100000;
		if (a[i].x%10==9) a[i].x+=10;
		a[i].y=y*100000;
		if (a[i].y%10==9) a[i].y+=10;
		a[i].x/=10; a[i].y/=10;
		//g<<a[i].x<<" "<<a[i].y<<"\n";
	}
}

bool cauta(st x)
{
	int st=1, dr=n, mij;
	bool ok=0;
	
	while (st<=dr && !ok)
	{
		mij=(st+dr)/2;
		if (a[mij].x==x.x && a[mij].y==x.y) ok=1;
		else if (a[mij].x<x.x || (a[mij].x==x.x && a[mij].y<x.y)) st=mij+1;
				else dr=mij-1;
	}
	
	return ok;
}

void Solve()
{
	int i, j, x, y;
	st p1, p2, s1, s2, j1, j2;
	for (i=1; i<n; ++i)
		for (j=i+1; j<=n; ++j)
		{
			p1=a[i]; p2=a[j];
			if (p1.x>p2.x) swap(p1, p2);
			//cout<<i<<" "<<j<<"\n";
			//caz I
			if (p1.y==p2.y)
			{
				j1=s1=p1; j2=s2=p2;
				if (p1.x<p2.x) x=p2.x-p1.x;
				else x=p1.x-p2.x;
				j1.y=j2.y=p1.y-x;
				s1.y=s2.y=p2.y+x;
			}
			//caz II
			if (p2.x==p1.x)
			{
				j1=s1=p1; j2=s2=p2;
				if (p2.y>p1.x) y=p2.x-p1.x;
				else y=p1.x-p2.x;
				j1.x=j2.x=p2.x+y;
				s1.x=s2.x=p1.x-y;
			}
			//caza III
			if (p2.y>p1.y)
			{
				x=p2.x-p1.x;
				y=p2.y-p1.y;
				s1.x=p1.x-y; s1.y=p1.y+x;
				s2.x=p2.x-y; s2.y=p2.y+x;
				j1.x=p1.x+y; j1.y=p1.y-x;
				j2.x=p2.x+y; j2.y=p2.y-x;
			}
			//cazul IV
			if (p1.y>p2.y)
			{
				x=p2.x-p1.x;
				y=p1.y-p2.y;
				s1.x=p1.x+y; s1.y=p1.y+x;
				s2.x=p2.x+y; s2.y=p2.y+x;
				j1.x=p1.x-y; j1.y=p1.y-x;
				j2.x=p2.x-y; j2.y=p2.y-x;
			}
			
			//perechea s
			if (cauta(s1) && cauta(s2)) ++nr;
			//perechea j
			if (cauta(j1) && cauta(j2)) ++nr;
			
		}
		g<<nr/4<<"\n";
}

bool cmp(st a, st b)
{
	if (a.x<b.x || (a.x==b.x && a.y<b.y)) return 1;
	return 0;
}

int main()
{
	Citeste();
	sort(a+1, a+n+1, cmp);
	Solve();
	f.close();
	g.close();
	return 0;
}