Pagini recente » Cod sursa (job #2525988) | Cod sursa (job #2526138) | Cod sursa (job #1856634) | Cod sursa (job #1313026) | Cod sursa (job #894125)
Cod sursa(job #894125)
#include <fstream>
#include <algorithm>
using namespace std;
#define x first
#define y second
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int maxn = 120001;
typedef pair<double, double> Point;
Point v[maxn];
Point stack[maxn];
int N;
inline int ccw(const Point& p1, const Point& p2, const Point& p3)
{
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
inline bool cmp(const Point &p1, const Point &p2)
{
return ccw(v[1], p1, p2) < 0;
}
void sortPoints()
{
int pos = 1;
for (int i = 2; i <= N; i++)
if (v[i] < v[pos])
pos = i;
swap(v[1], v[pos]);
sort(v+2, v+N+1, cmp);
}
int main()
{
in >> N;
for (int i = 1; i <= N; i++)
in >> v[i].x >> v[i].y;
sortPoints();
int top = 2;
stack[1] = v[1];
stack[2] = v[2];
for (int i = 3; i <= N; i++)
{
while (top >= 2 && ccw(stack[top], stack[top-1], v[i]) < 0) --top;
stack[++top] = v[i];
}
out << top << '\n';
out.setf(ios::fixed);
out.precision(9);
for (int i = top; i > 0; i--)
out << stack[i].x << ' ' << stack[i].y << '\n';
return 0;
}