Pagini recente » Cod sursa (job #1971090) | Cod sursa (job #564129) | Cod sursa (job #2262484) | Cod sursa (job #3222309) | Cod sursa (job #3162085)
#include <fstream>
#include <cmath>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int NMAX = 12e4;
struct Point
{
double x, y;
void Read()
{
cin >> x >> y;
}
};
int n;
Point points[NMAX + 1];
Point stack[NMAX + 1];
int stackIndex;
double CrossProduct(Point p1, Point p2, Point p3)
{
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
void Reverse(Point a[])
{
for(int i = 1, j = n; i < j; i++, j--)
swap(a[i], a[j]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
points[i].Read();
int bound = 2;
for(int rep = 0; rep < 2; rep++)
{
for(int i = 1; i <= n; i++)
{
while(stackIndex >= bound && CrossProduct(stack[stackIndex - 1], stack[stackIndex], points[i]) < 0)
stackIndex--;
stack[++stackIndex] = points[i];
}
stackIndex--;
bound += stackIndex;
Reverse(points);
}
for(int i = 1; i <= stackIndex; i++)
cout << stack[i].x << ' ' << stack[i].y << '\n';
return 0;
}