Pagini recente » Cod sursa (job #3303587) | Cod sursa (job #2044155) | Cod sursa (job #3347532) | Borderou de evaluare (job #1851512) | Cod sursa (job #2289329)
#include <stdio.h>
#include <utility>
#include <algorithm>
#include <stack>
struct Point {
double x, y;
};
using namespace std;
const int NMAX = 120005;
const double EPS = 1e-12;
int N;
Point points[NMAX];
bool vis[NMAX];
int st[NMAX];
int head = 0;
double cp(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
struct Point_cmp {
inline bool operator() (const Point& p1, const Point& p2) {
if (p1.x == p2.x) {
return p1.y < p2.y;
}
return p1.x < p2.x;
}
};
using namespace std;
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
scanf("%lf %lf", &points[i].x, &points[i].y);
}
st[++head] = 1;
st[++head] = 2;
vis[2] = true;
sort(points + 1, points + N + 1, Point_cmp());
for (int i = 3, p = 1; i > 0; i += (p = (i == N) ? -p : p)) {
if (vis[i]) {
continue;
}
while (head >= 2 && (cp(points[st[head - 1]], points[st[head]], points[i]) < EPS)) {
vis[st[head--]] = false;
}
st[++head] = i;
vis[i] = true;
}
printf("%d\n", head-1);
for (int i = 1; i < head; ++i) {
printf("%.6lf %.6lf\n", points[st[i]].x, points[st[i]].y);
}
fclose(stdin);
fclose(stdout);
return 0;
}