Pagini recente » Cod sursa (job #1967871) | Cod sursa (job #1713943) | Cod sursa (job #613920) | Cod sursa (job #968866) | Cod sursa (job #1040975)
#include <algorithm>
#include <bitset>
#include <fstream>
#define N 120002
#define EPS 1e-12
#define pc pair<double, double>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pc a[N];
bitset <N> v;
int inf[N];
double sarr(pc o, pc a, pc b)
{
return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
int main()
{
int n, i, sign=1;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i].x>>a[i].y;
}
sort(a+1, a+n+1);
v[2]=1;
inf[1]=1;inf[2]=2;inf[0]=2;
for(i=1;i;i+=sign)
{
if(!v[i])
{
while(inf[0]>1&&sarr(a[inf[inf[0]-1]], a[inf[inf[0]]], a[i])<EPS)
{
v[inf[inf[0]--]]=0;
}
inf[++inf[0]]=i;
v[i]=1;
}
if(i==n) sign=-1;
}
fout<<inf[0]-1<<"\n";
fout.precision(6);
fout<<fixed;
for(i=1;i<inf[0];i++)
{
fout<<a[inf[i]].x<<" "<<a[inf[i]].y<<"\n";
}
}