Cod sursa(job #1080814)

Utilizator vld7Campeanu Vlad vld7 Data 12 ianuarie 2014 22:17:35
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.61 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#define x first
#define y second

using namespace std;

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

const double EPS = 0.0001;

int n, ans;
vector < pair <double, double> > Point;

void read() {
	f >> n;
	for (int i = 1; i <= n; i++) {
		double x, y;
		f >> x >> y;
		Point.push_back (make_pair (x, y));
	}
}

bool equal (double a, double b) {
	if (abs (a - b) < EPS)
		return 1;
	return 0;
}

bool find (double x, double y) {
	int lo = 0, hi = n - 1;
	
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (equal (Point[mid].x, x)) {
			if (equal (Point[mid].y, y))
				return 1;
			else if (Point[mid].y < y)
				lo = mid + 1;
			else
				hi = mid - 1;
		} else if (Point[mid].x < x)
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	
	return 0;
}

void solve() {
	sort (Point.begin(), Point.end());
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++) {
			double x0, y0, x1, y1, x2, y2, x3, y3, dx, dy, midx, midy;
			
			x0 = Point[i].x;		y0 = Point[i].y;
			x1 = Point[j].x;		y1 = Point[j].y;
			
			midx = (x0 + x1) / 2;
			midy = (y0 + y1) / 2;
			
			dx = abs (midx - x0);
			dy = abs (midy - y0);
			
			if (y0 < y1) {
				x2 = midx + dy;
				y2 = midy - dx;
				x3 = midx - dy;
				y3 = midy + dx;
			} else {
				x2 = midx - dy;
				y2 = midy - dx;
				x3 = midx + dy;
				y3 = midy + dx;
			}
			
			if (find (x2, y2) && find (x3, y3))
				ans++;
		}
}

int main() {
	read();
	solve();
	
	g << ans / 2 << '\n';
	
	return 0;
}