Cod sursa(job #447324)

Utilizator savimSerban Andrei Stan savim Data 28 aprilie 2010 14:00:08
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define MAX_N 1510

int N, sol;

struct punct {
	double x, y;
} P[MAX_N], New, Midd;

inline int egal(double p, double q) {
	double diff = p - q;
	if (diff < 0) diff = -diff;

	if (diff < 0.001) return 1;
	return 0;
}

inline int cmp(punct A, punct B) {
	if (!egal(A.x, B.x)) return A.x < B.x;
	else return A.y < B.y;
}

inline double distanta(punct A, punct B) {
	return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

void search() {
	int st = 0, dr = N + 1, mid = 0;
	while (st + 1 < dr) {
    	mid = (st + dr) / 2;
		
		if (egal(P[mid].x, New.x)) {
			if (egal(P[mid].y, New.y)) {
            	sol++;
				return;
			}
			else 
				if (P[mid].y > New.y) dr = mid;
				else st = mid;
		}
		else 
			if (P[mid].x > New.x) dr = mid;
			else st = mid;
	}
}

int main() {

	freopen("triang.in", "r", stdin);
	freopen("triang.out", "w", stdout);

	scanf("%d", &N);	
	for (int i = 1; i <= N; i++)
		scanf("%lf %lf", &P[i].x, &P[i].y);

	sort(P + 1, P + N + 1, cmp);

	for (int i = 1; i < N; i++)
		for (int j = i + 1; j <= N; j++) {
        	double height = 1.0 * (distanta(P[i], P[j]) * sqrt(3)) / 2; 

			Midd.x = 1.0 * (P[i].x + P[j].x) / 2;
			Midd.y = 1.0 * (P[i].y + P[j].y) / 2;
			
			if (P[i].x == P[j].x) {
				New.x = Midd.x + height;
				New.y = Midd.y;
				search();

				New.x = Midd.x - height;
				search();
			}
			else 
				if (P[i].y == P[j].y) {
					New.x = Midd.x;
					New.y = Midd.y + height;
					search();

					New.y = Midd.y - height;
					search();
				}
				else {
                	double m = -1.0 * (P[j].x - P[i].x) / (P[j].y - P[i].y);
					double s = 1.0 * height / sqrt(1 + m * m);

					New.x = Midd.x + s;
					New.y = Midd.y + m * s;
					search();

					New.x = Midd.x - s;
					New.y = Midd.y - m * s;
					search();
				}
		}

	printf("%d\n", sol / 3);

	return 0;
}