Cod sursa(job #262780)

Utilizator scvalexAlexandru Scvortov scvalex Data 19 februarie 2009 17:21:23
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

typedef struct {
	double x, y;
} Point;

const double e = 1e-3;
const int pa = 1500;
const int pb = 1501;

int N;
Point P[1502];

#define abs(n) ((n < 0) ? (-n) : (n))

bool lt(const Point &a, const Point &b) {
	if (abs(a.x - b.x) < e)
		return ((b.y - a.y) > e);
	return ((b.x - a.x) > e);
}

inline double square(double n) {
	return n*n;
}

void calc_points(int i, int j) {
	double xm = (P[i].x + P[j].x) / 2.0,
	       ym = (P[i].y + P[j].y) / 2.0;
	double l2 = square(P[i].x - P[j].x) + square(P[i].y - P[j].y);
	if (P[j].y - P[i].y < e) {
		double dy = sqrt(l2 * (3.0/4.0));
		P[pa].x = P[pb].x = xm;
		P[pa].y = ym + dy;
		P[pb].y = ym - dy;
		return;
	}
	double mp = - (P[j].x - P[i].x) / (P[j].y - P[i].y);
	double dx = sqrt(l2 * (3.0 / 4.0) / (1.0 + mp));
	double dy = mp*dx;
	P[pa].x = xm + dx;
	P[pa].y = ym + dy;
	P[pb].x = xm - dx;
	P[pb].y = ym - dy;
}

void printp(int i) {
	printf("%.3lf %.3lf\n", P[i].x, P[i].y);
}

bool avem_echi(int n) {
	int nlog, i, l = 0;

	for (nlog = 0; (1<<nlog) < N; ++nlog)
		;
	for (i = nlog; i >= 0; --i)
		if ((l + (1<<i) < N) && (P[n].x - P[l + (1<<i)].x > -e)) {
			//printf("%.3f\n", P[n].x - P[l+(1<<i)].x);
			l += 1<<i;
		}

//	printf("%d\n", l);
//	printp(l);

	if ((l >= N) || (P[l].x - P[n].x > e))
		return false;

	for (i = nlog; i >= 0; --i)
		if ((l + (1<<i) < N) && (P[n].y - P[l + (1<<i)].y >= -e))
			l += 1<<i;
	
	return (P[l].y - P[n].y <= e);

}

int main(int argc, char *argv[]) {
	int i, j, t = 0;
	FILE *fi = fopen("triang.in", "r");
	fscanf(fi, "%d", &N);
	for (i = 0; i < N; ++i)
		fscanf(fi, "%lf %lf", &P[i].x, &P[i].y);
	fclose(fi);

	sort(P, P+N, lt);

	for (i = 0; i < N; ++i)
		for (j = i+1; j < N; ++j) {
			/*printp(i);
			printp(j);*/
			calc_points(i, j);
			/*printp(pa);
			printp(pb);
			printf("\n");*/

			/*if (avem_echi(pa) || avem_echi(pb))
				printf("TRIUNGHI ECHILATERAL!\n");
			printf("\n");*/
			t += avem_echi(pa) + avem_echi(pb);
		}

	FILE *fo = fopen("triang.out", "w");
	fprintf(fo, "%d\n", t/2);
	fclose(fo);

	return 0;
}