Pagini recente » Cod sursa (job #2485559) | Cod sursa (job #2248368) | Cod sursa (job #2061734) | Cod sursa (job #1376333) | Cod sursa (job #3139125)
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
// #define double float
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int INF = (1 << 30);
// ifstream cin("intersectiesegmente.in");
// ofstream cout("intersectiesegmente.out");
struct Point
{
double x, y;
void Read()
{
cin >> x >> y;
}
Point operator - (const Point& other) const
{
return { x - other.x, y - other.y };
}
double operator * (const Point& other) const
{
return x * other.y - y * other.x;
}
};
const int NMAX = 120000;
int n;
Point a[NMAX + 1];
Point st[NMAX + 1];
int ind;
int leftmost;
bool cmp(Point x, Point y)
{
return (x - a[1]) * (y - a[1]) < 0;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
a[i].Read();
leftmost = 1;
for(int i = 2; i <= n; i++)
if(make_pair(a[i].x, a[i].y) < make_pair(a[leftmost].x, a[leftmost].y))
leftmost = i;
swap(a[1], a[leftmost]);
sort(a + 2, a + n + 1, cmp);
st[++ind] = a[1];
st[++ind] = a[2];
for(int i = 3; i <= n; i++)
{
while(ind >= 2 && (st[ind] - st[ind - 1]) * (a[i] - st[ind - 1]) > 0)
ind--;
st[++ind] = a[i];
}
cout << ind << '\n';
for(int i = ind; i >= 1; i--)
cout << fixed << setprecision(9) << a[i].x << ' ' << a[i].y << '\n';
return 0;
}