Cod sursa(job #693858)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 27 februarie 2012 17:25:16
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<cstdio>
#include<vector>
#include<set>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
void read(),solve();
vector<pair<pair<int,int>,int> >V;
map<double,int> M;
int n,i,x,y,a,b,precalc[1010],SOL;
double ung;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		V.push_back(make_pair(make_pair(x,y),i));
	}
}
void solve()
{
	for(i=2;i<=n;i++)precalc[i]=precalc[i-1]+i-1;
	sort(V.begin(),V.end());
	for(vector<pair<pair<int,int>,int> >::iterator it=V.begin();it!=V.end()-1;it++)
	{
		a=(*it).first.first;
		b=(*it).first.second;
		for(vector<pair<pair<int,int>,int> >::iterator it1=it+1;it1!=V.end();it1++)
		{
			x=(*it1).first.first;
			y=(*it1).first.second;
			ung=atan2(double(y-b),double(x-a));
			M[ung]=M[ung]+1;
		}
	}
	for(map<double,int>::iterator it=M.begin();it!=M.end();it++)SOL+=precalc[it->second];
	printf("%d\n",SOL);
}