Cod sursa(job #402430)

Utilizator FlorianFlorian Marcu Florian Data 23 februarie 2010 21:00:34
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
using namespace std;
#include<fstream>
#include<vector>
#define EPS 1e-14
#define mk make_pair
#define x first
#define y second
#define ll long long
#define oo 0x3f3f3f3f
const int MAX_N = 1024;
vector<pair<int, int> > A;
ll SOL;
double P[MAX_N * MAX_N]; int N, K;
int tmp;
inline int comp(double a, double b)
{
	if(a + EPS < b) return 1; // a < b
	if(b + EPS < a) return -1; // b < a
	return 0;
}
inline double panta(pair<int, int> a, pair<int, int>b)
{	
	return (double)(a.y - b.y)/(double)(a.x - b.x);
}
int main()
{
	ifstream in("trapez.in"); ofstream out("trapez.out");
	in>>N;
	int i,a,b,j;
	for(i = 1; i <= N; ++i)
	{
		in>>a>>b;
		A.push_back(mk(a,b));
	}
	for(i = 0; i < N; ++i)
		for(j = i + 1; j < N; ++j)
			if(A[i].x == A[j].x ) ++tmp;
			else P[++K] = panta(A[i], A[j]);
	sort(P+1, P+K+1);
	i = 0, j = 0;
	while(i <= K)
	{
		while(i <= K && comp(P[i], P[j]) == 0) ++i;
		--i;
		SOL += 1LL*( i - j + 1 ) * (i - j) / 2;
		++i;
		j = i;
	}
	SOL += tmp*(tmp-1)/2;
	out<<SOL<<"\n";
	return 0;
}