Pagini recente » Cod sursa (job #1629415) | Cod sursa (job #2560050) | Cod sursa (job #2983518) | Cod sursa (job #1440760) | Cod sursa (job #2716455)
#include <iostream>
#include <iomanip>
#include <vector>
#include <fstream>
#include <algorithm>
#include <stack>
#define x first
#define y second
#define pb push_back
#define pdd pair<double,double>
#define pii pair<int,int>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
pdd sir[120005],t;
bool ok=0;
int n;
stack <pii> s;
double det(pdd a,pdd b,pdd c)
{
return (a.x*b.y+b.x*c.y+a.y*c.x-c.x*b.y-c.y*a.x-b.x*a.y);
}
vector<int>v,v1;
int main()
{
in>>n;
for(int i=1;i<=n;i++)
{
in>>sir[i].x>>sir[i].y;
}
sort(sir+1,sir+n+1);
s.push({0,1});
for(int i=2;i<=n;i++)
{
while(s.size()>1 && det(sir[s.top().x],sir[s.top().y],sir[i])<0.0)
{
s.pop();
}
s.push({s.top().y,i});
}
while(!s.empty())
{
v.pb(s.top().y);
s.pop();
}
s.push({0,1});
for(int i=2;i<=n;i++)
{
while(s.size()>1 && det(sir[s.top().x],sir[s.top().y],sir[i])>0.0)
{
s.pop();
}
s.push({s.top().y,i});
}
s.pop();
while(s.size()>1)
{
v1.pb(s.top().y);
s.pop();
}
out<<v.size()+v1.size()<<'\n';
out<<fixed<<setprecision(6);
for(int i=v.size()-1;i>=0;i--)
{
out<<sir[v[i]].x<<' '<<sir[v[i]].y<<'\n';
}
for(auto i:v1)
{
out<<sir[i].x<<' '<<sir[i].y<<'\n';
}
return 0;
}