Cod sursa(job #1993933)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 24 iunie 2017 00:19:06
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.26 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 "patrate3"
#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;

inline void rotation(point &A, double c, double s) {
	double nx = c * A.x - s * A.y;
	A.y = s * A.x + c * A.y;
	A.x = nx;
}

inline void transition(point &A, double x, double y) {
	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;
}

bool esq(point A, point B) {
	if (A.y < B.y) return false;
	double tx = -A.x, ty = -A.y;
	transition(A, tx, ty);
	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);
	rotation(B, c, s);
	double d = dst(A, B);
	point C = make_pair(A.x, d);
	point D = make_pair(B.x, d);
	rotation(C, c, -s);
	rotation(D, c, -s);
	transition(C, -tx, -ty);
	transition(D, -tx, -ty);
	return (exists(C) && exists(D));
}

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)
	if (esq(v[i], v[j])) ++ans;
	printf("%d\n", ans);
	return 0;
}