Pagini recente » Cod sursa (job #2145977) | Cod sursa (job #1576241) | Cod sursa (job #2658772) | Cod sursa (job #2649825) | Cod sursa (job #1959861)
#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 120000;
struct Point {
double x;
double y;
Point (int _x = INT_MAX, int _y = INT_MAX): x(_x), y(_y) {}
}bottom;
vector<Point> v;
int st[5 + MAX_N];
double cross_product(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}
int ccw(Point a, Point b, Point c) {
double cp = cross_product(a, b, c);
if (cp == 0)
return 0;
if (cp < 0)
return -1;
return 1;
}
int dist(Point a, Point b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool cmp(Point a, Point b) {
int cp = ccw(bottom, a, b);
if (cp == 0)
return dist(bottom, a) < dist(bottom, b);
if (cp == -1)
return false;
return true;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int N, poz = 0;
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
double x, y;
Point p;
scanf("%lf%lf", &x, &y);
p.x = x;
p.y = y;
if (bottom.y > y) {
bottom = p;
poz = i;
} else if (bottom.y == y && bottom.x > x) {
bottom = p;
poz = i;
}
v.push_back(p);
}
swap(v[poz], v[0]);
sort(v.begin() + 1, v.end(), cmp);
v.push_back(v[0]);
st[0] = 0;
st[1] = 1;
int ind = 2, top = 1;
while (ind < v.size()) {
int cp = ccw(v[st[top - 1]], v[st[top]], v[ind]);
if (cp == 0) {
st[top] = ind++;
} else if (cp == 1) {
st[++top] = ind++;
} else {
--top;
}
}
printf("%d\n", top);
for (int i = 0; i < top; ++i) {
printf("%.13lf %.13lf\n", v[st[i]].x, v[st[i]].y);
}
return 0;
}