Pagini recente » Cod sursa (job #493306) | Cod sursa (job #1254185) | Cod sursa (job #2393657) | Cod sursa (job #1946283) | Cod sursa (job #2989434)
#include <algorithm>
#include <iomanip>
#include <fstream>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef double TElem;
typedef pair<TElem, TElem> Point;
const int N_MAX = 120005;
const double EPS = 1e-12;
int N, head;
Point v[N_MAX];
int stack[N_MAX];
bool vis[N_MAX];
void write();
void read() {
f >> N;
for(int i = 1; i <= N; ++i) {
Point p;
f >> p.x >> p.y;
v[i] = p;
}
}
inline TElem cross_product(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
void solve() {
read();
sort(v+1, v+N+1);
stack[1] = 1, stack[2] = 2, head = 2;
vis[2] = true;
for(int i = 1, p = 1; i > 0; i += (p = (i == N? -p:p))) {
if(vis[i]) continue;
while(head >= 2 && cross_product(v[stack[head-1]], v[stack[head]], v[i]) < EPS) {
vis[stack[head--]] = false;
}
stack[++head] = i;
vis[i] = 1;
}
write();
}
void write() {
g << head - 1 << '\n';
g << setprecision(6) << fixed;
for(int i = 1; i < head; ++i) {
g << v[stack[i]].x << " " << v[stack[i]].y << '\n';
}
}
int main(void) {
solve();
}