Pagini recente » Cod sursa (job #2641355) | Cod sursa (job #2577778) | Cod sursa (job #2720297) | Cod sursa (job #133701) | Cod sursa (job #2314275)
#include <fstream>
#include <bits/stdc++.h>
#define Nmax 150005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
double vrg = 1e-12;
bool vis[Nmax];
int n, i;
int st[Nmax], top=2;
struct db{
double x, y;
}v[Nmax], 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);
}
bool cmp(db a, db b)
{
if ( a.x == b.x ) return a.y < b.y ;
return a.x < b.x ;
}
int main()
{
f >> n;
for ( i = 1 ; i <= n ; i++ )
{
f >> X.x >> X.y ;
v[i] = X;
}
sort( v+1, v+n+1, cmp);
st[1] = 1, st[2] = 2;
vis[2] = 1;
for ( i = 3 ; i <= n ; i++)
{
if( vis[i] == 1) continue;
while ( top >= 2 && pr(v[st[top]], v[st[top-1]], v[i]) < vrg )
{
vis[st[top]] = 0;
top--;
}
st[++top] = i;
vis[i] = i;
}
for ( i = n-1 ; i >= 1 ; i--)
{
if( vis[i] == 1) continue;
while ( top >= 2 && pr(v[st[top]], v[st[top-1]], v[i]) < vrg )
{
vis[st[top]] = 0;
top--;
}
st[++top]=i;
vis[i] = 1;
}
g << top-1 << '\n' << setprecision(12) << fixed;
for (int i = top-1; i >= 1; i--)
g << v[st[i]].x << " " << v[st[i]].y << '\n';
return 0;
}