Cod sursa(job #307931)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 25 aprilie 2009 16:46:55
Problema Trapez Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#define ll long long
#define mp make_pair
using namespace std;
ll x,y,nr;
int n,i,j;
typedef pair <ll,ll> p;
vector <p> a,hash;
inline ll cmmdc(ll a,ll b)
{
	if(!b) return a;
	return cmmdc(b,a%b);
}
inline int cmp(p x,p y)
{
	if((x.first<0||x.second<0)&&(y.first>=0&&y.second>=0))
		return 1;
	if((y.first<0||y.second<0)&&(x.first>=0&&x.second>=0))
		return 0;
	return 1LL*x.first*y.second<1LL*x.second*y.first;
}
int main()
{
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%lld%lld",&x,&y);
		a.push_back(mp(x,y));
	}
	for(i=0;i<n;i++)
		for(j=i+1;j<n;j++)
		{
			ll m=a[i].first-a[j].first;
			ll n=a[i].second-a[j].second;
			ll cd=cmmdc(m,n);
			hash.push_back(mp(n/cd,m/cd));
		}
	sort(hash.begin(),hash.end(),cmp);
	for(int q=1,DIM=hash.size();q<DIM;q++)
		if(hash[q].first==hash[q-1].first&&hash[q].second==hash[q-1].second)
			nr++;
	printf("%lld\n",nr);
	return 0;
}