Pagini recente » Cod sursa (job #1611275) | Cod sursa (job #1185519) | Cod sursa (job #1815169) | Monitorul de evaluare | Cod sursa (job #600029)
Cod sursa(job #600029)
# include <algorithm>
# include <bitset>
# include <cstdio>
# include <deque>
using namespace std;
typedef double db;
typedef pair <db, db> PR;
const char *FIN = "infasuratoare.in", *FOU = "infasuratoare.out";
const int MAX = 120005;
const db EPS = 1e-12;
# define x first
# define y second
int N;
PR V[MAX];
int check (db A, db B) {
if (B - A > EPS) return -1;
if (A - B > EPS) return 1;
return 0;
}
bool comp (PR A, PR B) {
if (check (A.x, B.x)) return check (A.x, B.x) < 0;
return check (A.y, B.y) < 0;
}
int in (PR A, PR B, PR C) {
return check ((A.y - B.y) * C.x + (B.x - A.x) * C.y + (A.x * B.y) - (B.x * A.y), 0);
}
void convexhull (void) {
deque <int> stk;
bitset <MAX> viz;
int wh = 1;
# define pb push_back
# define Pb pop_back
sort (V + 1, V + N + 1, comp);
stk.pb (1), stk.pb (2), viz[2] = 1;
for (int i = 3; viz[1] == 0; stk.pb (i), viz[i] = 1) {
for (; viz[i] ; i += wh = (i == N ? -1 : wh)) ;
for (; stk.size () > 1 && in (V[*(stk.end () - 2)], V[stk.back ()], V[i]) < 0; viz[stk.back ()] = 0, stk.Pb ());
}
printf ("%d\n", stk.size () - 1);
for (size_t i = 0, j = stk.size () - 1; i < j; ++i)
printf ("%lf %lf\n", V[stk[i]].x, V[stk[i]].y);
}
int main (void) {
freopen (FIN, "r", stdin);
freopen (FOU, "w", stdout);
scanf ("%d", &N);
for (int i = 1; i <= N; ++i)
scanf ("%lf %lf", &V[i].x, &V[i].y);
convexhull ();
}