Pagini recente » Cod sursa (job #2961172) | Cod sursa (job #4874) | Cod sursa (job #1756853) | Cod sursa (job #137036) | Cod sursa (job #1644175)
# include <cstdio>
# include <bitset>
# include <algorithm>
using namespace std;
FILE *fin = fopen("infasuratoare.in", "rt");
FILE *fout = fopen("infasuratoare.out", "wt");
const int EPS = 1e-12; // 1*10^(-12)
const int MAXN = 120005;
struct punct { double x, y; };
bitset<MAXN> viz;
punct v[MAXN];
int st[MAXN];
int n, k;
inline int cmps(double a, double b) {
if (a+EPS<b) return 1;
if (b+EPS<a) return -1;
return 0;
}
bool cmp(const punct& a, const punct& b) {
int tmp;
tmp = cmps(a.x, b.x);
if (tmp != 0)
return (tmp == 1);
return (cmps(a.y, b.y) == 1);
}
int semn(punct a, punct b, punct c) {
double A, B, C;
A = a.y - b.y;
B = b.x - a.x;
C = a.x * b.y - b.x * a.y;
return cmps(A*c.x + B*c.y + C, 0);
}
void infasuratoare() {
int inc, i;
sort(v+1, v+n+1, cmp);
st[1] = 1; // se initializeaza stiva cu primele 2 puncte
st[2] = 2;
k = 2;
i = 3;
viz[2] = 1;
inc = 1;
while (!viz[1]) { // nu s-a inchis infasuratoarea
while (viz[i]) {
if (i == n)
inc = -1;
i += inc;
}
while (k >= 2 && semn(v[st[k-1]], v[st[k]], v[i]) == -1) // daca se respecta proprietatea determinantului
viz[st[k--]] = 0;
st[++k] = i;
viz[i] = 1;
}
}
int main() {
int i;
fscanf(fin, "%d", &n);
for (i=1; i<=n; ++i)
fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
infasuratoare();
fprintf(fout, "%d\n", k-1);
for (i=2; i<=k; ++i)
fprintf(fout, "%lf %lf\n", v[st[i]].x, v[st[i]].y);
return 0;
}