Pagini recente » Cod sursa (job #2616129) | Cod sursa (job #947591) | Cod sursa (job #40640) | Cod sursa (job #2428743) | Cod sursa (job #2765856)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x,y;
}a[120020],q[120020];
double cross_product(punct a,punct b,punct c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(punct c,punct b)
{
return cross_product(a[1],c,b)<0;
}
int n,i,pos,vf;
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>a[i].x>>a[i].y;
pos=1;
for(i=2;i<=n;i++)
if(a[i].x<a[pos].x || (a[i].x==a[pos].x && a[i].y<a[pos].y))
pos=i;
swap(a[1],a[pos]);
sort(a+2,a+n+1,cmp);
q[1]=a[1];
q[2]=a[2];
vf=2;
for(i=3;i<=n;i++)
{
while(vf>=2 && cross_product(q[vf-1],q[vf],a[i])>0)
vf--;
vf++;
q[vf]=a[i];
}
g<<vf<<'\n';
for(i=vf;i>=1;i--)
g<<fixed<<setprecision(6)<<q[i].x<<" "<<q[i].y<<'\n';
}