Pagini recente » Cod sursa (job #619694) | Cod sursa (job #1295559) | Cod sursa (job #1897573) | Cod sursa (job #277643) | Cod sursa (job #2245742)
// InfasuratoareConvexa.cpp : Defines the entry point for the console application.
//
#include <cstdio>
#include <cstdlib>
#define EPS 0.000000000001
struct Point {
double x;
double y;
};
int n;
Point pct[120000];
int st[120000];
int head;
double crossProduct(Point*A, Point*B, Point*C) {
double res = (B->x - A->x)*(C->y - A->y) - (B->y - A->y)*(C->x - A->x);
return res;
}
int comparePoints(const void * a, const void * b) {
double prod = crossProduct(pct, (Point*)a, (Point*)b);
if (prod > 0) return -1;
return 1;
}
int main() {
FILE * fin;
FILE * fout;
int A;
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
fscanf(fin, "%d", &n);
fscanf(fin, "%lf%lf", &pct[0].x, &pct[0].y);
A = 0;
for (int i = 1; i < n; ++i) {
fscanf(fin, "%lf%lf", &pct[i].x, &pct[i].y);
if (pct[i].x < pct[A].x) {
A = i;
} else if ((pct[i].x == pct[A].x) && (pct[i].y < pct[A].y)) {
A = i;
}
}
if (A) {
double x, y;
x = pct[A].x;
pct[A].x = pct[0].x;
pct[0].x = x;
y = pct[A].y;
pct[A].y = pct[0].y;
pct[0].y = y;
}
qsort(pct + 1, n - 1, sizeof(Point), comparePoints);
head = -1;
st[++head] = 0;
st[++head] = 1;
for (int i = 2; i < n; ++i) {
while (head >= 2 && crossProduct(pct + st[head], pct + st[head-1], pct + i) > EPS) {
--head;
}
st[++head] = i;
}
fprintf(fout, "%d\n", head+1);
for (int i = 0; i <= head; i++)
{
fprintf(fout, "%f %f\n", pct[st[i]].x, pct[st[i]].y);
}
fclose(fin);
fclose(fout);
return 0;
}