Pagini recente » Cod sursa (job #70959) | Cod sursa (job #1707375) | Cod sursa (job #2271070) | Cod sursa (job #2392557) | Cod sursa (job #2373214)
#include <bits/stdc++.h>
#define point pair <double, double>
#define x first
#define y second
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int nMax = 120010;
const double EPS = 1e-12;
int n, i, h;
int st[nMax], vis[nMax];
point v[nMax];
bool check(point o, point a, point b)
{
return ((a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y) < EPS);
}
int main()
{
fin >> n;
for(i=1; i<=n; i++)
fin >> v[i].x >> v[i].y;
sort(v+1, v+n+1);
st[++h] = 1; st[++h] = 2;
vis[2] = true;
for(i=1; i<=n; i++)
{
if(vis[i] == true) continue;
while(h >= 2 && check(v[st[h-1]], v[st[h]], v[i]))
vis[st[h--]] = false;
st[++h] = i;
vis[i] = true;
}
for(i=n-1; i>0; i--)
{
if(vis[i] == true) continue;
while(h >= 2 && check(v[st[h-1]], v[st[h]], v[i]))
vis[st[h--]] = false;
st[++h] = i;
vis[i] = true;
}
fout << h-1 << '\n';
for(i=1; i<h; i++)
fout << v[st[i]].x << " " << v[st[i]].y << '\n';
return 0;
}