Pagini recente » Cod sursa (job #229662) | Cod sursa (job #1403585) | Cod sursa (job #2360245) | Cod sursa (job #1020365) | Cod sursa (job #1414390)
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int N=120004;
const double inf=1000000000;
#define pb push_back
int n,i,pos;
struct point{
double x,y, panta; };
bool cmp(point a, point b) { return a.panta < b.panta; }
point a[N],p;
vector<point> sol;
int cp(point _1, point _2, point _3)
{
return _1.x*_2.y + _2.x*_3.y + _3.x*_1.y -
_1.y*_2.x - _2.y*_3.x - _3.y*_1.x;
}
int main()
{
ios_base::sync_with_stdio(0);
cin>>n;
for (i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
p=a[1]; pos=1;
for (i=2;i<=n;i++)
if (a[i].x<p.x || (a[i].x==p.x && a[i].y<p.y)) p=a[i], pos=i;
swap(a[1],a[pos]);
for (i=2;i<=n;i++) a[i].panta=(a[i].x==a[1].x)?inf:(a[i].y-a[1].y)/(a[i].x-a[1].x);
sort(a+2,a+n+1,cmp);
sol.pb(a[1]);
sol.pb(a[2]);
for (i=3;i<=n;i++){
while (sol.size()>=2 & cp(sol[sol.size()-2],sol[sol.size()-1],a[i])<0) sol.pop_back();
sol.pb(a[i]);
}
cout<<sol.size()<<'\n';
cout<<fixed<<setprecision(10);
for (i=0;i<sol.size();i++) cout<<sol[i].x<<' '<<sol[i].y<<'\n';
return 0;
}