Pagini recente » Cod sursa (job #1695839) | Cod sursa (job #2756065) | Cod sursa (job #2466218) | Cod sursa (job #2080450) | Cod sursa (job #661780)
Cod sursa(job #661780)
#include <stdio.h>
#include <math.h>
long i, n, mm, mM, poz, k, ptc, dex[120010], j, pt[120010];
double x[120010], y[120010], A, B, C, max = 0;
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%ld", &n);
for (i = 1; i <= n; ++i) {
scanf("%lf %lf", &x[i], &y[i]);
if (max < y[i]) max = y[i], poz = i;
}
dex[poz] = 1;
pt[++ptc] = poz;
//prima dreapta
for (j = 1; j <= n; ++j) {
if (x[j] < x[poz] && !dex[j]) {
A = y[j] - y[poz];
B = x[poz] - x[j];
C = x[j] * y[poz] - x[poz] * y[j];
long mm = 0, mM = 0;
for (k = 1; k <= n; ++k) {
if (k != poz && k != j) {
if (A * x[k] + B * y[k] + C > 0) ++mM;
if (A * x[k] + B * y[k] + C < 0) ++mm;
}
}
if (mm == 0 || mM == 0) {
pt[++ptc] = j;
dex[j] = 1;
break;
}
}
}
for (i = 2; i <= ptc; ++i) {
for (j = 1; j <= n; ++j) {
if (!dex[j]) {
A = y[j] - y[pt[i]];
B = x[pt[i]] - x[j];
C = x[j] * y[pt[i]] - x[pt[i]] * y[j];
long mm = 0, mM = 0;
for (k = 1; k <= n; ++k) {
if (k != pt[i] && k != j) {
if (A * x[k] + B * y[k] + C > 0) ++mM;
if (A * x[k] + B * y[k] + C < 0) ++mm;
}
}
if (mm == 0 || mM == 0) {
pt[++ptc] = j;
dex[j] = 1;
break;
}
}
}
}
printf("%ld\n", ptc);
for (i = 1; i <= ptc; ++i) printf("%.6lf %.6lf\n", x[pt[i]], y[pt[i]]);
return 0;
}