Pagini recente » Cod sursa (job #1186946) | Cod sursa (job #551166) | Cod sursa (job #2363850) | Cod sursa (job #2743735) | Cod sursa (job #1963212)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 120003
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct puncte
{
double x,y;
}a[DIM],stiva[DIM];
int n,st;
void read()
{
f>>n;
for(int i=1;i<=n;i++)f>>a[i].x>>a[i].y;
f.close();
}
inline double product(puncte a,puncte b,puncte c){return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
inline bool cmp(puncte a1,puncte b){return product(a[1],a1,b)<0;}
void sortare()
{
int pos=1;
for(int i=2;i<=n;++i)if(a[pos].y>a[i].y||(a[pos].y==a[i].y&&a[pos].x>a[i].x))pos=i;
swap(a[1],a[pos]);
sort(a+2,a+n+1,cmp);
}
void solve()
{
sortare();
stiva[1]=a[1]; stiva[2]=a[2]; st=2;
for(int i=3;i<=n;i++)
{
while(st>=2&&product(stiva[st-1],stiva[st],a[i])>0)--st;
stiva[++st]=a[i];
}
}
void write()
{
g<<fixed;
g<<st<<'\n';
for(int i=st;i>=1;--i)
g<<setprecision(9)<<stiva[i].x<<" "<<stiva[i].y<<'\n';
g.close();
}
int main()
{
read();
solve();
write();
return 0;
}