Pagini recente » Cod sursa (job #738629) | Cod sursa (job #2480241) | Cod sursa (job #153812) | Cod sursa (job #865885) | Cod sursa (job #913089)
Cod sursa(job #913089)
#include<fstream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MaxN = 120005;
struct punct{
double x,y;
}p[MaxN];
int n,vfs,st[2*MaxN];
vector<punct> Vans;
struct cmp
{
bool operator()( const punct &a,const punct &b )
{
if( a.x != b.x )
return a.x < b.x;
return a.y < b.y;
}
};
double sarrus(punct a , punct b , punct c)
{
return a.x*b.y + b.x*c.y + c.x*a.y - b.y*c.x - b.x*a.y - a.x*c.y;
}
int main()
{
freopen("infasuratoare.in" , "r" , stdin);
freopen("infasuratoare.out" , "w" , stdout);
scanf("%d" , &n);
int i;
for( i = 1 ; i <= n ; i++ )
scanf("%lf%lf" , &p[i].x , &p[i].y);
sort(p+1,p+n+1,cmp());
vfs = 1; st[vfs] = 1;
st[++vfs] = 2;
for( i = 3 ; i <= n ; i++ )
{
while( vfs > 1 && sarrus(p[st[vfs-1]],p[st[vfs]],p[i]) < 0 )
vfs--;
st[++vfs] = i;
}
for( i = 1 ; i <= vfs ; i++ )
Vans.push_back(p[st[i]]);
vfs = 1; st[vfs] = n;
st[++vfs] = n-1;
for( i = n-2 ; i ; i-- )
{
while( vfs > 1 && sarrus(p[st[vfs-1]] , p[st[vfs]] , p[i]) < 0 )
vfs--;
st[++vfs] = i;
}
for( i = 2 ; i < vfs ; i++ )
Vans.push_back(p[st[i]]);
vector<punct>::iterator it,iend;
iend = Vans.end();
it = Vans.begin();
printf("%d\n" , Vans.size());
for( ; it != iend ; ++it )
printf("%lf %lf\n" , it->x , it-> y);
return 0;
}