Cod sursa(job #1081533)

Utilizator BuseSorinFMI Buse Sorin-Marian BuseSorin Data 13 ianuarie 2014 18:32:23
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct punct
{
	double x, y;
};
vector<punct> v;
int N, nr_p;
bool cmp(punct a, punct b)
{
	if (a.x  < b.x)return 1;
	if (a.x == b.x)return a.y < b.y;
	return 0;
}

bool cauta(punct c)
{
	int i, step;
	for (step = 1; step < N; step <<= 1);
	for (i = 0; step; step >>= 1)
	if (i + step < N && ((v[i + step].x - c.x) < -0.0001 || (abs(v[i + step].x - c.x) <= 0.0001 && v[i + step].y - c.y <= 0.0001)))
		i += step;
	if (abs(v[i].x - c.x) <= 0.0001 && abs(v[i].y - c.y) <= 0.0001) return 1;
	return 0;
}

int main()
{
	ifstream f("patrate3.in");
	ofstream o("patrate3.out");

	int i, j;
	f >> N;
	for (i = 1; i <= N; i++)
	{
		punct aux;
		f >> aux.x >> aux.y;
		v.push_back(aux);
	}
	sort(v.begin(), v.end(), cmp);
	for (i = 0; i < N - 1; i++)
	for (j = i + 1; j < N; j++)
	{
		punct mij, d, a, b;
		mij.x = (v[i].x + v[j].x) / 2;
		mij.y = (v[i].y + v[j].y) / 2;
		d.x = abs(mij.x - v[i].x);
		d.y = abs(mij.y - v[i].y);
		if (v[i].y < v[j].y)
		{
			a.x = mij.x + d.y;
			a.y = mij.y - d.x;
			b.x = mij.x - d.y;
			b.y = mij.y + d.x;
		}
		else
		{
			a.x = mij.x - d.y;
			a.y = mij.y - d.x;
			b.x = mij.x + d.y;
			b.y = mij.y + d.x;
		}
		int ok = 0;
		ok += cauta(a);
		if (ok) ok += cauta(b);
		if (ok == 2)nr_p++;
	}
	o << nr_p / 2;
	return 0;
}