Cod sursa(job #981156)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 6 august 2013 15:08:06
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb

#include <cstdio>
#include <utility>
#include <algorithm>

typedef std::pair<int,int> Point;

const int MAX_N(1001);
const int MAX_VALUE(1 << 30);
const double GUARD(0.0000001);

struct Line
{
	double slope;
	double a;
	double b;
	double c;
} v [MAX_N * MAX_N];

bool operator < (struct Line a, struct Line b)
{
	return a.slope < b.slope;
}

int n, end, Result;
Point p [MAX_N];

inline void Read (void)
{
	std::freopen("trapez.in","r",stdin);
	std::scanf("%d",&n);
	end = (n * (n - 1)) >> 1;
	for (int index(1) ; index <= n ; ++index)
		std::scanf("%d %d",&p[index].first,&p[index].second);
	std::fclose(stdin);
}

inline void Print (void)
{
	std::freopen("trapez.out","w",stdout);
	std::printf("%d\n",Result);
	std::fclose(stdout);
}

inline bool Intersect (struct Line x, struct Line y)
{
	return x.a * y.b - x.b * y.a;
}

inline void Compute (void)
{
	int i, j, index(1);
	for (i = 1 ; i <= n ; ++i)
		for (j = i + 1 ; j <= n ; ++j)
		{
			v[index].a = p[j].second - p[i].second;
			v[index].b = p[i].first - p[j].first;
			v[index].c = v[index].a * p[i].first + v[index].b * p[i].second;
			if (p[i].first == p[j].first)
				v[index].slope = MAX_VALUE;
			else
				v[index].slope = (p[j].second - p[i].second) / (p[j].first - p[i].first);
			++index;
		}
	std::sort(v + 1,v + end + 1);
	i = 1;
	while (i <= end)
	{
		for (j = i + 1 ; j <= end && v[j].slope >= v[i].slope - GUARD && v[j].slope <= v[i].slope + GUARD ; ++j)
			/* do nothing */;
		if (v[i].slope == 0)
		{
			int k;
			while (i < j)
			{
				for (k = i + 1 ; k < j ; ++k)
					if (!Intersect(v[i],v[k]))
						++Result;
				++i;
			}
		}
		else
		{
			Result += ((j - i) * (j - i - 1)) >> 1;
			i = j;
		}
	}
}

int main (void)
{
	Read();
	Compute();
	Print();
	return 0;
}