Pagini recente » Cod sursa (job #2384726) | Cod sursa (job #50756) | Cod sursa (job #36916) | Cod sursa (job #1961126) | Cod sursa (job #2863163)
#include <bits/stdc++.h>
#define N 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
};
int n,top;
punct a[N],stv[N];
/**
ABxAC=[(xB-xA)i+(yB-yA)j]x[(xC-xA)i+(yC-yA)j]
(xB-xA)(yC-yA)k-(yB-yA)(xC-xA)k
*/
double produs_vectorial(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 comp(punct p1,punct p2)
{
return produs_vectorial(a[1],p1,p2)<0;
}
int main()
{
int i,poz=1;
fin>>n;
for(i=1;i<=n;i++)
fin>>a[i].x>>a[i].y;
for(i=2;i<=n;i++)
if(a[i].x<a[poz].x || a[i].x==a[poz].x && a[i].y<a[poz].y) poz=i;
swap(a[1],a[poz]);
sort(a+2,a+n+1,comp);
stv[1]=a[1];stv[2]=a[2];
top=2;
for(i=3;i<=n;i++)
{
while(top>=2 && produs_vectorial(stv[top-1],stv[top],a[i])>0) top--;
stv[++top]=a[i];
}
fout<<top<<"\n";
for(i=top;i>=1;i--)
fout<<fixed<<setprecision(9)<<stv[i].x<<" "<<stv[i].y<<"\n";
return 0;
}