Pagini recente » Diferente pentru implica-te/arhiva-educationala intre reviziile 174 si 223 | Cod sursa (job #235864) | Cod sursa (job #3291374) | Cod sursa (job #226687) | Cod sursa (job #3293744)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Pct
{
double x,y;
bool t;
}p[120000];
bool sortpct(Pct a,Pct b)
{
return (a.x<b.x || (a.x==b.x && a.y<b.y));
}
double Arie(Pct a,Pct b,Pct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-b.x*a.y-c.x*b.y-a.x*c.y;
}
vector<Pct>s;
int main()
{
int n;
fin>>n;
for(int i=0;i<n;i++)
fin>>p[i].x>>p[i].y;
sort(p,p+n,sortpct);
for(int i=1;i<n-1;i++)
p[i].t=(Arie(p[0],p[n-1],p[i])>0);
s.push_back(p[0]);
for(int i=1;i<n;i++)
{
if(p[i].t)
continue;
if(s.size()==1)
s.push_back(p[i]);
else
{
while(s.size()>=2 && Arie(s[s.size()-2],p[i],s[s.size()-1])>0)
s.pop_back();
s.push_back(p[i]);
}
}
int size0=s.size();
p[0].t=1;
for(int i=n-1;i>=0;i--)
{
if(!p[i].t)
continue;
if(s.size()==size0)
s.push_back(p[i]);
else
{
while(s.size()-size0>=1 && Arie(s[s.size()-2],p[i],s[s.size()-1])>0)
s.pop_back();
s.push_back(p[i]);
}
}
s.pop_back();
fout<<s.size()<<'\n';
fout<<fixed<<setprecision(6);
for(int i=0;i<s.size();i++)
fout<<s[i].x<<' '<<s[i].y<<'\n';
return 0;
}