Pagini recente » Cod sursa (job #1438767) | Cod sursa (job #1393329) | Cod sursa (job #2740505) | Cod sursa (job #1570899) | Cod sursa (job #2044398)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nmax 120005
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x, y;
} a[nmax];
int n;
int st[nmax], top;
bool viz[nmax]; /// v[i] =1 daca este pe stiva
/// returneaza < 0 daca pct a[p] este in semiplanul - al dreptei det. de pct (a[i],a[j])
/// + daca e in semiplanul +
/// a[i] = A; a[j] = B
double F(int i, int j, int p)
{
return a[p].x*(a[i].y-a[j].y) + a[p].y*(a[j].x-a[i].x) + a[i].x*a[j].y - a[j].x*a[i].y;
/*a[1].x = a[1].y = 0; /// originea
a[2].x = a[2].y = 6; /// bisectoare
a[3].x = 7; a[3].y = 7;
cout << F(1,2,3);*/
}
inline bool cmp(punct a, punct b)
{
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
/// algoritmul lui Hill
void Hill()
{
sort(a+1, a+n+1, cmp);
st[++top] = 1;
st[++top] = 2;
viz[2] = 1;
for(int i = 3; i <= n; ++i)
{
while(top > 1 && F(st[top-1], st[top], i) < 0)
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
for(int i = n-1; i >= 1; --i)
if(viz[i] == 0)
{
while(F(st[top-1], st[top], i) < 0)
{
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
}
void afisare()
{
fout << top-1 << '\n';
for(int i = 1; i < top; ++i)
fout << setprecision(12) << fixed << a[st[i]].x << " " << a[st[i]].y << '\n';
fout.close();
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> a[i].x >> a[i].y;
fin.close();
Hill();
afisare();
return 0;
}