Cod sursa(job #7028)

Utilizator tvladTataranu Vlad tvlad Data 21 ianuarie 2007 11:55:01
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 9-a si gimnaziu Marime 2.2 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

struct punct {
	float x;
	float y;
};

const int N = 1000;
const double prec = 0.000005;
int n;
punct a[N];

bool cmp ( punct a, punct b ) {
	return (a.x == b.x) ? a.y < b.y : a.x < b.x;
}

void patrat ( punct a, punct b, punct &c, punct &d ) {
// vertical
	if (a.x == b.x) {
		c.y = (a.y + b.y) / 2;
		d.y = c.y;
		c.x = a.x - fabs((b.y - a.y) / 2);
		d.x = a.x + fabs((b.y - a.y) / 2);
		return;
	}
// orizontal
	if (a.y == b.y) {
		c.x = (a.x + b.x) / 2;
		d.x = c.x;
		c.y = a.y - fabs((b.x - a.x) / 2);
		d.y = a.y + fabs((b.x - a.x) / 2);
		return;
	}
// caz general
	punct p;	p.x = (a.x + b.x) / 2.0;	p.y = (a.y + b.y) / 2.0;
	double v = (b.x - a.x)*(b.x - a.x) / 4.0 + (b.y - a.y)*(b.y - a.y) / 4.0;
	double m2 = (a.x - b.x) / (b.y - a.y);
	double w = p.y - m2*p.x;
	double t = p.x*p.x + p.y*p.y - v;
	double a1 = m2*m2 + 1;
	double b1 = m2*w - p.x -m2*p.y;
	double c1 = w*w - 2*w*p.y + t;
	double delta = b1*b1 - a1*c1;
	double sqd = sqrt(delta);
	double x1 = ( -b1 - sqd ) / a1;
	double x2 = ( -b1 + sqd ) / a1;
	c.x = x1;
	d.x = x2;
	if (c.x > d.x) {
		double aux = c.x;
		c.x = d.x;
		d.x = aux;
	}
	d.y = ( m2 * ( d.x - c.x ) + 2*p.y ) / 2;
	c.y = 2*p.y - d.y;
	if ((m2 < 0 && c.y < d.y) || (m2 > 0 && c.y > d.y)) {
		double aux = c.y;
		c.y = d.y;
		d.y = aux;
	}
}

bool eq ( float a, float b ) {
	return (-prec < (a-b) && (a-b) < prec);
}

bool caut ( int st, int dr, punct x ) {
	if (dr-st <= 1) {
		if ( eq(a[st].x, x.x) && eq(a[st].y, x.y)) return true;
		if ( eq(a[dr].x, x.x) && eq(a[dr].y, x.y)) return true;
		return false;
	}
	int mj = (st+dr)/2;
	if (cmp(x, a[mj])) {
		return caut(st, mj, x);
	} else {
		return caut(mj, dr, x);
	}
}

int main() {
	freopen("patrate3.in","r",stdin);
	freopen("patrate3.out","w",stdout);

	scanf("%d",&n);
	for (int i = 0; i<n; ++i) {
		scanf("%f %f",&a[i].x,&a[i].y);
	}

	sort(a, a+n, cmp);

	punct x, y;
	int rez = 0;
	for (int i = 0; i<n; ++i) {
		for (int j = i+1; j<n; ++j) {
			patrat(a[i],a[j],x,y);
			rez += (caut(0, n-1, x) && caut(0, n-1, y));
		}
	}
	rez /= 2;
	printf("%d\n",rez);
	return 0;
}