Pagini recente » Cod sursa (job #612183) | Cod sursa (job #2749261) | Cod sursa (job #2309952) | Cod sursa (job #1607511) | Cod sursa (job #1413993)
#include <bits/stdc++.h>
using namespace std;
#ifdef INFOARENA
ifstream f("infasuratoare.in");
#define cout g
#else
ifstream f("date.in");
#endif // INFOARENA
ofstream g("infasuratoare.out");
struct punct{double x,y;};
int n,pos,i,st;
punct p[120001],stiva[120001];
double cross_prod(punct A,punct B,punct C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
inline bool cmp(punct A,punct B)
{
return cross_prod(p[1],A,B)<0;
}
int main()
{
f>>n;
for(i=1;i<=n;++i)
{
f>>p[i].x>>p[i].y;
if(pos==0 || p[pos].x>p[i].x || p[pos].x==p[i].x && p[pos].y>p[pos].y) pos=i;
}
swap(p[pos],p[1]);
sort(p+2,p+n+1,cmp);
for(i=1;i<=n;++i)
{
while(st>1 && cross_prod(stiva[st-1],stiva[st],p[i])<0) --st;
stiva[++st]=p[i];
}
cout<<st<<'\n';
for(i=1;i<=st;++i) cout<<fixed<<stiva[i].x<<' '<<stiva[i].y<<'\n';
return 0;
}