Cod sursa(job #73520)

Utilizator scapryConstantin Berzan scapry Data 19 iulie 2007 10:18:10
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <cassert>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define printf(...) /*don't hold me back I want to fall*/;

enum { maxpoints = 1501, maxcoord = 20002, coord_bias = 10001 };

const double eps = 1e-3;
double sin60, cos60, sin_60, cos_60;

inline bool equal(double a, double b)
{
	return fabs(a - b) < eps;
}

struct Point
{
	double x, y;

	bool operator<(const Point &p) const
	{
		if(equal(x, p.x))
			return y < p.y;
		else
			return x < p.x;
	}
} point[maxpoints];
int points;
int ans;

void init()
{
	sin60 = sin(M_PI / 3);
	cos60 = cos(M_PI / 3);

	sin_60 = sin(-M_PI / 3);
	cos_60 = cos(-M_PI / 3);
}

void search(double x, double y)
{
	Point look;
	look.x = x - eps / 2;
	look.y = -1e20; //-inf

	printf("searching for x %lf y %lf\n", x, y);

	Point *it = lower_bound(point, point + points, look);

	while(it != point + points && equal(it->x, x))
	{
		if(equal(it->y, y))
		{
			printf("found %lf %lf\n", it->x, it->y);
			ans++;
			break; //?
		}
		it++;
	}
}

void go()
{
	int i, j;
	double oldx, oldy;
	double x, y;

	init();
	sort(point, point + points);

	printf("sorted points:\n");
	for(i = 0; i < points; i++)
		printf("%lf %lf\n", point[i].x, point[i].y);
	printf("\n");

	for(i = 0; i < points; i++)
		for(j = i + 1; j < points; j++)
		{
			printf("i %d (%lf %lf) j %d (%lf %lf)\n", i, point[i].x, point[i].y,
					j, point[j].x, point[j].y);

			oldx = point[j].x - point[i].x;
			oldy = point[j].y - point[i].y;

			//forward 60deg
			x = oldx * cos60 - oldy * sin60;
			y = oldx * sin60 + oldy * cos60;
			x += point[i].x;
			y += point[i].y;
			search(x, y);

			//backward 60deg
			x = oldx * cos_60 - oldy * sin_60;
			y = oldx * sin_60 + oldy * cos_60;
			x += point[i].x;
			y += point[i].y;
			search(x, y);

			printf("\n");
		}

	printf("pre ans %d\n", ans);
	assert(ans % 3 == 0);
	ans /= 3;
}

int main()
{
	int i;
	FILE *f = fopen("triang.in", "r");
	if(!f) return 1;

	fscanf(f, "%d", &points);
	for(i = 0; i < points; i++)
	{
		fscanf(f, "%lf", &point[i].x);
		//tmp += coord_bias;

		fscanf(f, "%lf", &point[i].y);
		//tmp += coord_bias;
	}

	fclose(f);
	f = fopen("triang.out", "w");
	if(!f) return 1;

	go();

	fprintf(f, "%d\n", ans);
	fclose(f);
	return 0;
}