Seletiva IOI 2007

parallel.cpp

// Ivan Carvalho
// Paralelogramo - Seletiva IOI - OBI 2007
// O(n^2 * log(n))
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
map<ii, map<double,int> > tab;
map<ii,int > special;
map<ii,int> freq;
int X[1001],Y[1001];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&X[i],&Y[i]);
		for(int j = 1;j < i;j++){
			int dy = Y[i] - Y[j];
			int dx = X[i] - X[j];
			ii par = ii(X[i]+X[j],Y[i]+Y[j]);
			freq[par]++;
			if(dx == 0){
				special[par]++;
				continue;
			}
			tab[par][double(dy)/double(dx)]++;
		}
	}
	int resp = 0;
	for(auto it = tab.begin();it != tab.end();it++){
		ii par = (*it).first;
		for(auto segit = (*it).second.begin();segit != (*it).second.end();segit++){
			int qtd = (*segit).second;
			resp += qtd*(freq[par] - qtd);
		}
	}
	for(auto it = special.begin();it != special.end();it++){
		ii par = (*it).first;
		int qtd = (*it).second;
		resp += qtd*(freq[par] - qtd);
	}
	printf("%d\n",resp/2);
	return 0;
}