Cod sursa(job #1445499)

Utilizator tudorcomanTudor Coman tudorcoman Data 30 mai 2015 14:12:09
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb

#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;

const double eps = 0.0001;
const double infi = 1e20;

struct Point {
	double x, y;

	void Read() {
		double a, b;
		scanf("%lf %lf",&a,&b);
		x = a, y = b;
	}

}v[1001];

inline bool smaller (double x, double y) {
	return x - y < -eps;
}
inline bool equal (double x, double y) {
	return fabs(x - y) < eps;
}

inline bool bigger (double x, double y) {
	return !smaller(x, y) and !equal(x, y);
}

struct cmp {

	inline bool operator () (const Point& A, const Point& B) {
		if (equal(A.x, B.x))
			return smaller(A.y, B.y);
		return smaller(A.x, B.x);
	}
};

bool binary(int st, int dr, const Point& target) {

	if (st > dr)
		return 0;

	int mij = (st + dr) >> 1;

	if(equal(v[mij].x, target.x) and equal(v[mij].y, target.y))
		return true;

	if (equal(v[mij].x, target.x) and smaller(v[mij].y, target.y))
		return binary(mij + 1, dr, target);

	else if (equal(v[mij].x, target.x))
		return binary(st, mij - 1, target);

	else if (smaller(v[mij].x, target.x))
		return binary(mij + 1, dr, target);

	 
	return binary (st, mij - 1, target);

}

int main () {

	freopen( "patrate3.in", "r", stdin );
	freopen( "patrate3.out", "w", stdout );
	int N, Ans = 0;;
	scanf("%d", &N);

	for (register int i = 1; i <= N; ++ i)
		v[i].Read();

	sort(v + 1, v + N + 1, cmp());

	for (register int i = 1; i <= N; ++ i)
		for (register int j = i + 1; j <= N; ++ j) {

			Point mij, p1, p2;

			mij.x = (v[i].x + v[j].x) * 0.5;
			mij.y = (v[i].y + v[j].y) * 0.5;

			double a = fabs(mij.x - v[i].x), b = fabs(mij.y - v[i].y);

			if (bigger(v[i].y, v[j].y)) {
				p1.x = mij.x - b;
				p1.y = mij.y - a;
				p2.x = mij.x + b;
				p2.y = mij.y + a;
			} else {
				p1.x = mij.x + b;
				p1.y = mij.y - a;
				p2.x = mij.x - b;
				p2.y = mij.y + a;
			}

			Ans += (binary(1, N, p1) and binary(1, N, p2));
		}

	Ans >>= 1;
	printf("%d\n", Ans);
	return 0;
}