Cod sursa(job #1702994)

Utilizator kaesarioDumi Loghin kaesario Data 15 mai 2016 22:22:56
Problema Trapez Scor 60
Compilator c Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int m1, m2;
} t_slope;

int comp_lines(const void *a, const void *b) {
	t_slope *la = (t_slope*)a;
	t_slope *lb = (t_slope*)b;
	if (la->m1 == lb->m1)
		return (la->m2 - lb->m2);
	return la->m1 - lb->m1;
}

int gcd(int a, int b) {
	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int main() {
	int i, j, k, n, *x, *y, m1, m2, sign, d;
	t_slope *lines;

	FILE* f = fopen("trapez.in", "rt");
	fscanf(f, "%d", &n);
	x = (int*)malloc(n * sizeof(int));
	y = (int*)malloc(n * sizeof(int));
	for (i=0; i<n; i++)
		fscanf(f, "%d %d", x+i, y+i);
	fclose(f);

	lines = (t_slope*)malloc(n * (n+1) / 2 * sizeof(t_slope));
	k = 0;
	for (i=0; i<n-1; i++)
		for (j=i+1; j<n; j++) {
			m1 = y[j] - y[i];
			m2 = x[j] - x[i];
			if (m1 < 0) {
				sign = -1;
				m1 = -m1;
			}
			else
				sign = 1;

			if (m2 == 0) {
				m1 = 1;
				sign = 1;
			}
			else
				if (m2 < 0) {
					sign = -sign;
					m2 = -m2;
				}

			if (m1 == 0) {
				sign = 1;
				m2 = 0;
			}

			if (m1 > 1 && m2 > 1) {
				do {
					d = gcd(m1, m2);
					m1 = m1 / d;
					m2 = m2 / d;
				}
				while (d > 1);
			}

			lines[k].m1 = sign * m1;
			lines[k].m2 = m2;
			k++;
		}

	qsort(lines, k, sizeof(t_slope), comp_lines);

//	for (i=0; i<k; i++)
//			printf("%d/%d\n", lines[i].m1, lines[i].m2);

	n = 0;
	for (i=0; i<k-1;) {
		j = i+1;
		while (j < k && comp_lines(lines+i, lines+j) == 0) {
			j++;
			n++;
		}
		i = j;
	}

	f = fopen("trapez.out", "wt");
	fprintf(f, "%d", n);
	fclose(f);

	free(x);
	free(y);
	free(lines);

	return 0;
}