Pagini recente » Clasament 12345678910 | Cod sursa (job #2583269) | Cod sursa (job #561394) | Cod sursa (job #1730584) | Cod sursa (job #1922607)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int NMAX=120001;
typedef pair<double, double> point;
point v[NMAX], st[NMAX];
int n;
inline double cp(const point &a, const point &b, const point &c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
inline int cmp(const point &a, const point &b)
{
return cp(v[1], a, b)<0;
}
void sorting()
{
int p=1;
for(int i=2; i<=n; i++)
if(v[i]<v[p])
p=i;
swap(v[1], v[p]);
sort(v+2, v+n+1, cmp);
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
in>>n;
for(int i=1; i<=n; i++)
in>>v[i].x>>v[i].y;
sorting();
st[1]=v[1];
st[2]=v[2];
int top=2;
for(int i=3; i<=n; i++)
{
while(top>=2 && cp(st[top-1], st[top], v[i])>0)
top--;
st[++top]=v[i];
}
out<<top<<'\n';
for(int i=top; i>=1; i--)
out<<setprecision(8)<<fixed<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}