Pagini recente » Cod sursa (job #1979183) | Cod sursa (job #1754798) | Cod sursa (job #1026331) | Cod sursa (job #1556931) | Cod sursa (job #1702994)
#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;
}