Cod sursa(job #196627)

Utilizator coderninuHasna Robert coderninu Data 27 iunie 2008 16:19:15
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
#include <cmath>
#define err 0.0001

using namespace std;

typedef pair< long double, long double > punct;

int N, i, j, rez;
long double x, y;
vector< punct > pct;
punct P;

const long double cst = sqrtl(3) / 2;

inline long double modul(long double x) { return x<0?-x:x; }
inline int egal(punct p1, punct p2) { return (modul(p1.first - p2.first) <= err && modul(p1.second - p2.second) <= err); }
struct compare { bool operator()(punct p1, punct p2) { return (p1.first < p2.first || (p1.first == p2.first && p1.second <= p2.second)); } };
inline int comp(punct p1, punct p2){ return (p1.first < p2.first || (p1.first == p2.first && p1.second <= p2.second)); }
inline long double sqr(long double x) { return x*x; }
inline long double dist(punct p1,punct p2) { return sqrtl(sqr(p1.first - p2.first) + sqr(p1.second - p2.second)); } 
 
punct getPct(punct, punct);
int binSearch(int,int);

void afis(vector< pair< long double, long double > > a)
{
	for (vector< pair< long double, long double > >::iterator it = a.begin(); it != a.end(); ++it)
		printf("{ %Lf %Lf }  ", it->first, it->second);
	printf("\n");
}

void afis(pair< long double, long double > a)
{
	printf("[ %Lf %Lf ]\n", a.first, a.second);
}

int main()
{
	for(freopen("triang.in", "r", stdin), scanf("%d\n", &N), pct.reserve(N), i = 0; i<N; ++i) 
	{
		scanf("%Lf %Lf", &x, &y);
		pct.push_back(make_pair(x,y));
	}
	sort(pct.begin(),pct.end(),compare());
	for (i = 0; i<N-2; ++i)
		for (j = i+1; j<N-1; ++j)
		{
			P = getPct(pct[i],pct[j]);
			if (binSearch(j+1,N-1))
				++rez;
		}
	fprintf(fopen("triang.out", "w"), "%d", rez);
	return 0;
}

punct getPct(punct p1, punct p2)
{
	punct M, temp;
	M.first = (p1.first + p2.first) / 2;
	M.second = (p1.second + p2.second) / 2;
	long double l = dist(p1,p2)*cst;
	long double alfa = atan2(p1.first - p2.first, p2.second - p1.second);
	temp = make_pair(M.first + l*cos(alfa), M.second + l*sin(alfa));
	if (comp(p2,temp)) return temp;
	return make_pair(M.first - l*cos(alfa), M.second - l*sin(alfa));
}

int binSearch(int st, int dr)
{
	if (st > dr) return 0;
	int m = (st + dr) >> 1;
	if (egal(pct[m],P)) return 1;
	if (st == dr)
	{
		if (egal(pct[st],P)) return 1;
		return 0;
	}
	if (st + 1 == dr)
	{
		if (egal(pct[st],P) || egal(pct[dr],P)) return 1;
		return 0;
	}
	if (comp(pct[m],P)) return binSearch(m,dr);
	else return binSearch(st,m);
}