Pagini recente » Cod sursa (job #2596536) | Cod sursa (job #2806117) | Cod sursa (job #2744244) | Cod sursa (job #1092700) | Cod sursa (job #1327965)
#include <fstream>
#include<algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,a[120000],viz[120000],q;
struct punct
{
float x,y;
}v[1200000];
bool cmp(punct a,punct b)
{
if(a.x==b.x)
return a.y<b.y;
else
return a.x<b.x;
}
int main()
{
f>>n;
for(int i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
a[1]=1;
a[2]=2;viz[2]=1;q=2;
for(int i=3;i<=n;i++)
{
if((v[a[q]].x-v[a[q-1]].x)*(v[i].y-v[a[q-1]].y)-(v[a[q]].y-v[a[q-1]].y)*(v[i].x-v[a[q-1]].x)<0)
{a[++q]=i;
viz[i]=1;
}
else
{
while((v[a[q]].x-v[a[q-1]].x)*(v[i].y-v[a[q-1]].y)-(v[a[q]].y-v[a[q-1]].y)*(v[i].x-v[a[q-1]].x)>=0)
viz[q--]=0;
a[++q]=i;
}
}
for(int i=n;i>=1;i--)
if((v[a[q]].x-v[a[q-1]].x)*(v[i].y-v[a[q-1]].y)-(v[a[q]].y-v[a[q-1]].y)*(v[i].x-v[a[q-1]].x)<0)
{a[++q]=i;
viz[i]=1;
}
else
{
while((v[a[q]].x-v[a[q-1]].x)*(v[i].y-v[a[q-1]].y)-(v[a[q]].y-v[a[q-1]].y)*(v[i].x-v[a[q-1]].x)>=0)
viz[q--]=0;
a[++q]=i;
}
g<<q-1<<'\n';
g<<setprecision(6)<< fixed;
for(int i=q-1;i>=1;i--)
g<<v[a[i]].x<<" "<<v[a[i]].y<<'\n';
return 0;
}