Cod sursa(job #63567)

Utilizator ZweisteinAdrian VELICU Zweistein Data 29 mai 2007 17:13:04
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>
#define NPUNCTE 1001L
struct punct { long long x, y; };
struct segment { punct p1, p2; };
int sfunc (const void * s1, const void * s2) {
	segment * ss1=(segment *)s1;
	segment * ss2=(segment *)s2;
	long long a = ss1->p2.y - ss1->p1.y;
	long long b = ss1->p2.x - ss1->p1.x;
	  if (b<0) {a=-a; b=-b;};
	long long c = ss2->p2.y - ss2->p1.y;
	long long d = ss2->p2.x - ss2->p1.x;
	  if (d<0) {c=-c; d=-d;};
//	  return (a*d-b*c);
    return ((a*d>b*c)?1:(a*d==b*c?0:-1));
//	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) );
};
inline long long Combinanari(long long n) {
	if (n<2) return 0;
	else { return ((n*(n-1))/2); };
};
segment seg[NPUNCTE*NPUNCTE]; long segs;
int main (void) {
	FILE * fi = fopen("trapez.in","rt");
	FILE * fo = fopen("trapez.out","wt");
    int n;
	fscanf(fi,"%d",&n);
	punct p[NPUNCTE];
	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++) {
			seg[segs].p1=p[i];
			seg[segs].p2=p[j];
			segs++;			
		}
	qsort(seg,segs,sizeof(segment),sfunc); //!!!
	long pz=0; long off=1;
	long long rasp=0;
	while (pz+off<segs) {
		while ( (sfunc(&seg[pz],&seg[pz+off])==0) && (pz+off<segs) ) {
			off++;
		};
		rasp+= (off*(off-1))/2; // Combinanari(off);
		pz=pz+off; off=1;
	};
//	fprintf(stderr,"%lld",NPUNCTE*NPUNCTE);
	fprintf(fo,"%lld\n",rasp); 
	fclose(fi); fclose(fo);
};