Pagini recente » Cod sursa (job #268806) | Cod sursa (job #2688548) | Cod sursa (job #193810) | Cod sursa (job #1547329) | Cod sursa (job #3301131)
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
#define MAX 190000
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int c, stack[MAX], top, start;
double minX, minY = 1e18 / 1.0;
struct Point {
long double x, y;
} points[MAX];
bool cmp(const Point &a, const Point &b) {
return a.x * b.y >= b.x * a.y;
}
bool check(Point a, Point b, Point c) {
long double cross = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
return cross > 0;
}
void read() {
f >> c;
for (int i = 0; i < c; i++) {
f >> points[i].x >> points[i].y;
if ((points[i].y < minY) || (points[i].y == minY && points[i].x < minX)) {
minY = points[i].y;
minX = points[i].x;
start = i;
}
}
for (int i = 0; i < c; i++) {
points[i].x -= minX;
points[i].y -= minY;
}
}
void solve() {
swap(points[0], points[start]);
sort(points + 1, points + c, cmp);
stack[top++] = 0;
stack[top++] = 1;
for (int i = 2; i < c; i++) {
while (top >= 2 && !check(
points[stack[top - 2]],
points[stack[top - 1]],
points[i])) {
top--;
}
stack[top++] = i;
}
}
void print() {
g << top << "\n";
g << fixed << setprecision(10);
for (int i = 0; i < top; i++) {
g << points[stack[i]].x + minX << " "
<< points[stack[i]].y + minY << "\n";
}
}
int main() {
read();
solve();
print();
return 0;
}