Pagini recente » Cod sursa (job #118687) | Cod sursa (job #1604394) | Cod sursa (job #1980373) | Cod sursa (job #656796) | Cod sursa (job #600047)
Cod sursa(job #600047)
# include <algorithm>
# include <fstream>
# include <deque>
# include <iomanip>
using namespace std;
typedef double db;
typedef pair <db, db> PR;
const char *FIN = "infasuratoare.in", *FOU = "infasuratoare.out";
const int MAX = 120005, hg = 1 << 13;
const db EPS = 1e-12;
ifstream f (FIN);
ofstream g (FOU);
# define verf ++poz == hg ? fread ( ch, 1, hg, stdin ), poz = 0 : 0
# define x first
# define y second
int N;
PR V[MAX];
inline int check (db A, db B) {
if (B - A > EPS) return -1;
if (A - B > EPS) return 1;
return 0;
}
bool comp (const PR &A, const PR &B) {
int X = check (A.x, B.x);
if (X) return X < 0;
return check (A.y, B.y) < 0;
}
inline 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);
}
deque <int> stk;
bool viz[MAX];
void convexhull (void) {
int wh = 1;
sort (V + 1, V + N + 1, comp);
stk.push_back (1), stk.push_back (2), viz[2] = 1;
for (int i = 3; viz[1] == 0; stk.push_back (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.pop_back ());
}
g << stk.size () - 1 << "\n";
g << setprecision (6) << fixed;
for (size_t i = 0, j = stk.size () - 1; i < j; ++i)
g << V[stk[i]].x << " " << V[stk[i]].y << "\n";
}
int main (void) {
f >> N;
for (int i = 1; i <= N; ++i)
f >> V[i].x >> V[i].y;
convexhull ();
}