Cod sursa(job #430387)

Utilizator nandoLicker Nandor nando Data 30 martie 2010 22:39:32
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>

using namespace std;

FILE* fin=fopen("trapez.in","r");
FILE* fout=fopen("trapez.out","w");

typedef long long int64;

#define MAX 1000

vector<pair<int64,int64> > vec;
int n;
pair<int64,int64> pts[MAX];

int comp(pair<int64,int64> p1,pair<int64,int64> p2){
	typedef long double ld;
	ld a=(ld)p1.first/(ld)p1.second;
	ld b=(ld)p2.first/(ld)p2.second;

	if(abs(a-b)<=1e-15){
		return 0;
	}else{
		return a-b;
	}
}
void prep_frac(pair<int64,int64>& p){
//	if(p.second<0){
//		p.second=abs(p.second);
//		p.first*=-1L;
//	}
}
int main(){
	fscanf(fin,"%d ",&n);

	for(int i=0;i<n;i++){
		int64 x,y;
		fscanf(fin,"%lld %lld",&x,&y);
		pts[i]=make_pair(x,y);
	}

	int npx=0,npy=0;
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			pair<int64,int64>p=make_pair(pts[i].second-pts[j].second,pts[i].first-pts[j].first);
			if(p.second==0){
				npy++;
			}else if(p.first==0){
				npx++;
			}else{
				prep_frac(p);
				vec.push_back(p);
			}
		}
	}
	sort(vec.begin(),vec.end(),comp);

	int64 res=(npy-1)*npy/2+(npx-1)*npx/2;
	
	for(unsigned i=0;i<vec.size();i++){
		int k=0;
		while(vec[i].first*vec[i+k+1].second==vec[i+k+1].first*vec[i].second&&i+k+1<vec.size()){
			k++,i++;
		}
		if(k!=0){
			res+=k*(k+1)/2;
		}
	}
	fprintf(fout,"%lld ",res);
	fclose(fin);
	fclose(fout);
	return 0;
}