Cod sursa(job #594920)

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

struct punct {
	long long x,y;
};

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

bool cmp(punct a,punct b) {
	return (long long)a.x*b.y<(long long)a.y*b.x;
}

bool cmmp(punct a,punct b) {
	return (long long)a.x*b.y==(long long)a.y*b.x;
}

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].x=p[j].y - p[i].y;
				pan[nr].y=p[j].x - p[i].x;
			}
		}
	sort(&pan[1],&pan[nr+1],cmp);
	nrr=1;
	for(i=2;i<=n;++i) {
		if(cmmp(pan[i],pan[i-1]))
			++nrr;
		else {
			nrmax+=(nrr*(nrr-1))>>1;
			nrr=1;
		}
	}
	nrmax+=(nrr*(nrr-1))>>1;
	nrmax+=unu*(unu-1)>>1; nrmax=doi*(doi-1)>>1;
	printf("%lld\n",nrmax);
	return 0;
}