Cod sursa(job #1076950)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 10 ianuarie 2014 19:04:09
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.11 kb
#include <fstream>
#include <algorithm>
#define MAXN 1000
using namespace std;

struct Punct {
	int x, y;
}puncte[MAXN];

int N, patrate;

void input() {
	ifstream in("patrate3.in");
	in >> N;
	string numere;
	getline(in, numere);

	for (int i = 0; i < N; ++i) {
		getline(in, numere);

		int size = numere.size();
		bool spatiu = 0;
		puncte[i].x = puncte[i].y = 0;
		int semn1 = 1, semn2 = 1;

		for (int j = 0; j < size; ++j) {
			if (numere[j] == '.') {
				continue;
			}

			if (numere[j] == '-') {
				if (!spatiu) {
					semn1 = -1;
				} else {
					semn2 = -1;
				}
				continue;
			}

			if (numere[j] == ' ') {
				spatiu = 1;
				continue;
			}

			if (!spatiu) {
				puncte[i].x = puncte[i].x * 10 + numere[j] - '0';
			} else {
				puncte[i].y = puncte[i].y * 10 + numere[j] - '0';
			}
		}

		puncte[i].x *= 10, puncte[i].y *= 10;
		puncte[i].x *= semn1, puncte[i].y *= semn2;
	}

	in.close();
}

bool compare(const Punct &i, const Punct &j) {
	if (i.x == j.x) {
		return i.y < j.y;
	}
	return i.x < j.x;
}

bool binSearch(const Punct &p) {
	int left = 0, right = N - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (puncte[mid].x == p.x && puncte[mid].y == p.y) {
			return 1;
		}

		if (compare(puncte[mid], p)) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return false;
}

void solve() {
	sort(puncte, puncte + N, compare);

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (puncte[i].x <= puncte[j].x || puncte[i].y <= puncte[j].y) {
				continue;
			}

			int x1 = puncte[i].x, y1 = puncte[i].y, x2 = puncte[j].x, y2 = puncte[j].y;
			int xc = (x1 + x2) / 2, yc = (y1 + y2) / 2, xd = (x1 - x2) / 2, yd = (y1 - y2) / 2;
			int x3 = (xc - yd), y3 = yc + xd, x4 = xc + yd, y4 = (yc - xd);
			Punct p3, p4;
			p3.x = x3, p3.y = y3, p4.x = x4, p4.y = y4;

			if (binSearch(p3) && binSearch(p4)) {
				++patrate;
			}
		}
	}
}

inline void output() {
	ofstream out("patrate3.out");
	out << patrate;
	out.close();
}

int main() {
	input();
	solve();
	output();
	return 0;
}