Pagini recente » Cod sursa (job #2784537) | Cod sursa (job #1785315) | Cod sursa (job #2187413) | Cod sursa (job #2406262) | Cod sursa (job #1097983)
#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <algorithm>
#define nmax 120005
#define infinit 0x3f3f3f3f
using namespace std;
struct punct
{
float x, y;
};
punct puncte[nmax];
int n;
int pozstart; //pozitia elementului care nu trebuie introdus in coada de prioritati.
double rotatie(const punct& a, const punct& b, const punct& c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
struct cmp
{
bool operator()(const punct& a, const punct& b)
{
return rotatie(puncte[pozstart], a, b) > 0;
}
};
void citire()
{
scanf("%d\n", &n);
int xmin = infinit, ymin = infinit;
for(int i = 1; i <= n; ++i)
{
scanf("%f %f\n", &puncte[i].x, &puncte[i].y);
if(puncte[i].x < xmin)
{
pozstart = i;
xmin = puncte[i].x;
ymin = puncte[i].y;
}
else
if(puncte[i].x == xmin && puncte[i].y < ymin)
{
pozstart = i;
xmin = puncte[i].x;
ymin = puncte[i].y;
}
}
swap(puncte[1], puncte[pozstart]);
// for(int i = 1; i <= n; i++)
// cout << puncte[i].x << ' ' << puncte[i].y << '\n';
// cout << "\n\n";
sort(puncte+2, puncte+n+1, cmp());
}
punct stiva[nmax];
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
stiva[1] = puncte[1];
stiva[2] = puncte[2];
int k = 2;
for(int i = 3; i <= n; ++i)
{
while(rotatie(stiva[k-1], stiva[k], puncte[i]) < 0)
k--;
stiva[++k] = puncte[i];
}
// for(int i = 1; i <= n; i++)
// cout << puncte[i].x << ' ' << puncte[i].y << '\n';
cout << k << '\n';
cout.precision(12);
for(int i = 1; i <= k; i++)
cout << stiva[i].x << ' ' << stiva[i].y << '\n';
return 0;
}