Pagini recente » Cod sursa (job #3299442) | Cod sursa (job #2294606) | Cod sursa (job #2541547) | Cod sursa (job #1456137) | Cod sursa (job #3299446)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,nr;
struct punct
{
long double x,y;
}v[120012],primul,act;
long double aria(punct a,punct b,punct c)
{
a.x-=c.x;
a.y-=c.y;
b.x-=c.x;
b.y-=c.y;
return (a.x*b.y-a.y*b.x)/2.0;
}
bool crt(punct a,punct b)
{
return aria(primul,a,b)>0;
}
stack<punct> s,rez;
int main()
{
fin>>n;
fin>>v[1].x>>v[1].y;
primul=v[1];
for(int i=2; i<=n; i++)
{
fin>>v[i].x>>v[i].y;
if(v[i].y<primul.y)
primul=v[i];
else if(v[i].y==primul.y)
primul.x=min(primul.x,v[i].x);
}
sort(v+1,v+n+1,crt);
s.push(primul);
for(int i=1; i<=n; i++)
{
if(!(primul.x==v[i].x && primul.y==v[i].y) && s.size()==1)
s.push(v[i]);
else if(!(primul.x==v[i].x && primul.y==v[i].y))
{
act=s.top();
s.pop();
if(!s.empty() && aria(s.top(),act,v[i])>=0)
{
s.push(act);
s.push(v[i]);
}
else
s.push(v[i]);
}
}
memset(v,0,sizeof(v));
while(!s.empty())
{
rez.push(s.top());
s.pop();
nr++;
}
fout<<nr<<'\n';
while(!rez.empty())
{
fout<<fixed<<setprecision(6)<<rez.top().x<<' '<<rez.top().y<<'\n';
rez.pop();
}
return 0;
}