Pagini recente » Cod sursa (job #2246080) | Cod sursa (job #19609) | Cod sursa (job #533989) | Cod sursa (job #1521127) | Cod sursa (job #1420255)
#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.y<b.y || (a.y==b.y && a.x<b.x));
}
};
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]);
}
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()-1<<"\n";
for (int i=0;i<St.size()-1;++i) cout<<fixed<<setprecision(13)<<St[i].x<<" "<<St[i].y<<"\n";
return 0;
}