Cod sursa(job #63561)

Utilizator ZweisteinAdrian VELICU Zweistein Data 29 mai 2007 16:11:57
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#include <stdlib.h>
#define NPUNCTE 1000
struct punct { int x, y; };
struct segment { punct p1, p2; };
int sfunc (const void * s1, const void * s2) {
	segment * ss1=(segment *)s1;
	segment * ss2=(segment *)s2;
	return ( (ss1->p2.y - ss1->p1.y)*(ss2->p2.x-ss2->p1.x) < 
		 (ss1->p2.x - ss1->p1.x)*(ss2->p2.y-ss2->p1.y) );
//	return ( (ss1->p1->x*ss2->y) - (ss1->y*ss2->x) );
};
long Combinanari(long n, long k) {
	if (n<k) return 0;
	else { long r=1;
		for (long i=k+1; i<=n; i++) r*=i;
		for (long i=1; i<=n-k; i++) r/=i;
		return r;
	};
};
int main (void) {
	FILE * fi = fopen("trapez.in","rt");
	FILE * fo = fopen("trapez.out","wt");
//	int d;
	long n;
	fscanf(fi,"%ld",&n);
	punct p[NPUNCTE];
	segment seg[NPUNCTE*NPUNCTE]; long segs;
	for (int i=1; i<=n; i++) {
		fscanf(fi,"%ld %ld",&p[i].x,&p[i].y);
	};
	for (int i=1; i<n; i++) 
		for (int j=i+1; j<=n; j++) {
			segs++;
			seg[segs].p1=p[i];
			seg[segs].p2=p[j];
		}
	qsort(seg,segs,sizeof(segment),sfunc); //!!!
	int pz=0; int off=0;
	long rasp=0;
	while (pz+off<=segs) {
		while (sfunc(&seg[pz],&seg[pz+off])==0) {
			off++;
		};
		off--;
		rasp+=Combinanari(off+1,2);
	};
	fprintf(fo,"%ld\n",rasp);
	fclose(fi); fclose(fo);
};