Pagini recente » Cod sursa (job #1616890) | Cod sursa (job #3277671) | Cod sursa (job #248288) | Cod sursa (job #2762364) | Cod sursa (job #664278)
Cod sursa(job #664278)
#include<fstream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MaxN = 120001;
const char InFile[] = "infasuratoare.in";
const char OutFile[] = "infasuratoare.out";
int n,vfs,st[MaxN << 1];
struct punct{
double x,y;
} P[MaxN];
vector<punct> V;
bool cmp(punct a , 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()
{
ifstream fin ( InFile );
ofstream fout ( OutFile );
fin >> n;
int i;
for( i = 1 ; i <= n ; i++ )
fin >> P[i].x >> P[i].y;
fin.close();
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 )
V.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 )
V.push_back(P[st[i]]);
vector<punct>::iterator it,iend;
iend = V.end();
fout << V.size() << '\n';
for( it = V.begin() ; it != iend ; ++it )
fout << it -> x << ' ' << it -> y << '\n';
fout.close();
return 0;
}