Pagini recente » Cod sursa (job #1814677) | Cod sursa (job #98478) | Cod sursa (job #2500187) | Cod sursa (job #2399680) | Cod sursa (job #1382963)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMax 120010
#define INF (1<<31) - 1
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, top;
struct mPoint
{
double x;
double y;
} points[NMax], stack[NMax], lowPoint;
double angle(const mPoint &p1, const mPoint &p2, const mPoint &p3)
{
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
int cmp(const mPoint &p1, const mPoint &p2)
{
return angle(lowPoint, p1, p2) < 0;
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++)
f >> points[i].x >> points[i].y;
int pos = 1;
for (int i = 1; i <= n; i++) {
if (points[i].x < points[pos].x || (points[i].x == points[pos].x && points[i].y < points[pos].y))
pos = i;
}
swap(points[1], points[pos]);
sort(points + 2, points + n + 1, cmp);
stack[1] = points[1];
stack[2] = points[2];
top = 2;
for (int i = 3; i <= n; i++) {
while (top >= 2 && angle(stack[top - 1], stack[top], points[i]) > 0)
top--;
stack[++top] = points[i];
}
g << top << "\n";
for (int i = top; i >= 1; i--)
g << setprecision(12) << stack[i].x << " " << stack[i].y << "\n";
return 0;
}