Pagini recente » Cod sursa (job #1120899) | Cod sursa (job #1835146) | Cod sursa (job #2048806) | Cod sursa (job #1346165) | Cod sursa (job #3301134)
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
using namespace std;
#define MAX 150005
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int c, stack[MAX], top, start;
long double minX, minY = 1e18;
struct Point {
long double x, y;
} points[MAX];
long double cross(const Point &O, const Point &A, const Point &B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
long double dist2(const Point &A, const Point &B) {
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
bool cmp(const Point &a, const Point &b) {
long double c = cross(points[0], a, b);
if (abs(c) < 1e-12) {
return dist2(points[0], a) < dist2(points[0], b);
}
return c > 0;
}
void read() {
f >> c;
for (int i = 0; i < c; i++) {
f >> points[i].x >> points[i].y;
if ((points[i].y < minY) || (abs(points[i].y - minY) < 1e-12 && points[i].x < minX)) {
minY = points[i].y;
minX = points[i].x;
start = i;
}
}
}
void solve() {
swap(points[0], points[start]);
sort(points + 1, points + c, cmp);
stack[top++] = 0;
if (c > 1)
stack[top++] = 1;
for (int i = 2; i < c; i++) {
while (top >= 2 && cross(points[stack[top - 2]], points[stack[top - 1]], points[i]) <= 1e-12) {
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 << " " << points[stack[i]].y << "\n";
}
}
int main() {
read();
solve();
print();
return 0;
}