Pagini recente » Cod sursa (job #3125059) | Cod sursa (job #2344821) | Cod sursa (job #1468530) | Cod sursa (job #1885873) | Cod sursa (job #2295254)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define Nmax 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
bool vis[Nmax];
int n;
int st[Nmax], top=2;
struct db{
double x, y;
}v[Nmax], X;
bool cmp(db a, db b)
{
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
double pr(db a, db b, db c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++)
{
f >> X.x >> X.y;
v[i]=X;
}
sort(v+1, v+n+1, cmp);
//g << v[1].x << " " << v[1].y;
st[1]=1, st[2]=2; top=2;
vis[2]=1;
for (int i = 1; i <= n; i++)
{
if(vis[i] == 1) continue;
while(top >= 2 && pr(v[st[top]], v[st[top-1]], v[i]) < 0)
vis[st[top--]]=0;
st[++top]=i;
vis[i]=1;
}
for (int i = n; i >= 1; i--)
{
if(vis[i] == 1) continue;
while(top >= 2 && pr(v[st[top]], v[st[top-1]], v[i]) < 0)
vis[st[top--]]=0;
st[++top]=i;
vis[i]=1;
}
g << top-1 << '\n' << setprecision(6) << fixed;
for (int i = 1; i < top; i++)
g << v[st[i]].x << " " << v[st[i]].y << '\n';
return 0;
}