Cod sursa(job #395219)

Utilizator klamathixMihai Calancea klamathix Data 12 februarie 2010 15:58:22
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define f first
#define s second
#define p pair
#define pb push_back
#define mp make_pair
#define INF 2000000000
#define ll long long
using namespace std;

const double eps = 0.000000000001;
int i ,j , a , b, n;
ll int rez ,cnt , verti;
vector < p < int , int > > v;
vector < p < p < int , int > , p < int , int > > > seg;
vector < p < p < int , int > , p < int , int > > > vert;

inline double panta ( p < p <int ,int> , p<int ,int> > A ) {
	if ( A.s.f != A.f.f)
	return (double) (A.s.s - A.f.s ) / ( A.s.f - A.f.f );
	else return INF;
}

inline bool comp ( p < p <int,int> ,p<int,int> > x , p < p <int,int> , p <int, int> > y ) {
	return ( panta(x) - panta(y) < eps );
}


int main()
{
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	
	for( scanf("%d",&n); n-- ; ) {
		scanf("%d %d",&a,&b);
		v.pb(mp(a,b));
	}
	
	n = v.size();
	
	for( i = 0 ; i < n ; ++i )
		for( j = i + 1 ; j < n ; ++j ) {
			seg.pb( mp ( v[i] , v[j] ));
			if ( panta (seg.back()) == INF ) verti++, seg.pop_back();
		}
			
	sort ( seg.begin() , seg.end() , comp );
	
	for ( i = 0 ; i < seg.size() ; ++i ) {
		if ( i > 0 && panta(seg[i]) != panta(seg[i - 1])) {
				rez +=  cnt * ( cnt - 1 ) >> 1;
				cnt = 1;
		}
		else cnt++;
	}
	
	rez += cnt * ( cnt - 1 ) >> 1;
	rez += verti * (verti - 1) >> 1;
	
	printf("%lld\n",rez);
		
	
	//for (i = 0 ; i < seg.size() ; ++i )
	//	printf("%d %d %d %d\n",seg[i].f.f , seg[i].f.s , seg[i].s.f , seg[i].s.s );
	
	
return 0;
}