Cod sursa(job #1993925)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 24 iunie 2017 00:07:49
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cassert>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <list>
#include <functional>
using namespace std;
typedef long long LL;

#ifdef INFOARENA
#define ProblemName "something"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

#define MAXN 1010
typedef pair<double, double> point;
int N;
#define x first
#define y second

point v[MAXN];
const double pi = 4 * atan(1);
const double eps = 1e-9;

point rotation(point A, double c, double s) {
	return make_pair(c * A.x - s * A.y, s * A.x + c * A.y);
}

point transition(point A, double x, double y) {
	return make_pair(A.x + x, A.y + y);
}

double dst(point &A, point &B) {
	double dx = A.x - B.x, dy = A.y - B.y;
	return sqrt(dx * dx + dy * dy);
}

bool exists(point &A) {
	int left = lower_bound(v, v + N, make_pair(A.x - eps, 0.0)) - &v[0];
	if (fabs(A.x - v[left].x) >= eps)
		return false;
	int right = upper_bound(v, v + N, make_pair(A.x + eps, 0.0)) - &v[0];
	int i = lower_bound(v + left, v + right, make_pair(v[left].x, A.y - eps)) - &v[0];
	if (i == N)
		return false;
	if (fabs(A.y - v[i].y) >= eps)
		return false;
	return true;
}

int nrsq(point A, point B) {
	if (A.x > B.x) swap(A, B);
	double tx = -A.x, ty = -A.y;
	A = transition(A, tx, ty);
	B = transition(B, tx, ty);
	double phi;
	if (B.x > B.y)
		phi = atan(B.y / B.x);
	else phi = pi / 2 - atan(B.x / B.y);
	double c = cos(phi), s = -sin(phi);
	B = rotation(B, c, s);
	double d = dst(A, B);
	int ans = 0;
	for (int i = 1; i >= -1; i -= 2) {
		point C = make_pair(A.x, d * i);
		point D = make_pair(B.x, d * i);
		C = rotation(C, c, -s);
		D = rotation(D, c, -s);
		C = transition(C, -tx, -ty);
		D = transition(D, -tx, -ty);
		if (exists(C) && exists(D))
			++ans;
	}
	return ans;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OuFile, "w", stdout));
	scanf("%d", &N);
	for (int i = 0; i < N; ++i)
		scanf("%lf%lf", &v[i].x, &v[i].y);
	sort(v, v + N);
	int ans = 0;
	for (int i = 0; i < N; ++i)
	for (int j = i + 1; j < N; ++j)
		ans += nrsq(v[i], v[j]);
	printf("%d\n", ans / 4);
	return 0;
}