Cod sursa(job #594915)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 10 iunie 2011 14:57:30
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<stdio.h>
#include<algorithm>
#define N 1001
using namespace std;

struct punct {
	long long x,y;
};

punct p[N];
int pan[N*N];
int n,nr,unu,doi;
long long nrr,nrmax;

int main() {
	int i,j;
	freopen("trapez.in","r",stdin);
	freopen("trapez.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d%d",&p[i].x,&p[i].y);
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j) if(i!=j) {
			if(p[j].y - p[i].y == 0)
				++unu;
			else if(p[j].x - p[i].x == 0)
				++doi;
			else
				pan[++nr]=((p[j].y - p[i].y)*1000)/(p[j].x - p[i].x);
		}
	sort(&pan[1],&pan[nr+1]);
	nrr=1;
	for(i=2;i<=n;++i) {
		if(pan[i]==pan[i-1])
			++nrr;
		else {
			nrmax+=(nrr*(nrr-1))>>1;
			nrr=1;
		}
	}
	nrmax+=unu*(unu-1)>>1; nrmax=doi*(doi-1)>>1;
	printf("%lld\n",nrmax);
	return 0;
}