Pagini recente » Cod sursa (job #1972399) | Cod sursa (job #2444641) | Clasament cls_9_simulare_oji | Cod sursa (job #1547347) | Cod sursa (job #1420259)
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-13;
int n;
double a,b;
struct point
{
double x,y;
} p[120013];
vector < point > St;
struct comp
{
bool operator() (const point &a,const point &b)
{
return (a.x<b.x || (a.x==b.x && a.y<b.y));
}
};
int det(point a,point b,point c)
{
return (a.x*b.y - a.y*b.x +
b.x*c.y - c.x*b.y +
c.x*a.y - a.x*c.y );
}
int main(void)
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
for (int i=1;i<=n;++i)
{
cin>>a>>b;
p[i]={a,b};
}
sort(p+1,p+n+1,comp());
St.push_back(p[1]);
St.push_back(p[2]);
for (int i=3;i<=n;++i)
{
while (!St.empty() && det(St[St.size()-1],St[St.size()-2],p[i])>0) St.pop_back();
St.push_back(p[i]);
}
for (int i=n-1;i>=1;--i)
{
while (!St.empty() && det(St[St.size()-1],St[St.size()-2],p[i])>0) St.pop_back();
St.push_back(p[i]);
}
/*
St.push_back(p[n-1]);
for (int i=n-2;i>=1;--i)
{
while (!St.empty() && det(St[St.size()-1],St[St.size()-2],p[i])<=0) St.pop_back();
St.push_back(p[i]);
}*/
cout<<St.size()<<"\n";
for (int i=0;i<St.size();++i) cout<<fixed<<setprecision(13)<<St[i].x<<" "<<St[i].y<<"\n";
return 0;
}