Pagini recente » Cod sursa (job #2284217) | Cod sursa (job #2472395) | Cod sursa (job #846683) | Cod sursa (job #129033) | Cod sursa (job #729921)
Cod sursa(job #729921)
#include <fstream>
#include <algorithm>
using namespace std;
const int N=100005;
int stack[N],n;
bool use[N];
struct Punct
{
double x,y;
} a[N];
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
inline bool cmp(const Punct &a,const Punct &b)
{
return a.x<b.x || a.x==b.x && a.y<b.y;
}
inline void print(Punct &x)
{
out<<x.x<<" "<<x.y<<"\n";
}
inline int cross(Punct A,Punct B,Punct C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
void del(Punct &C)
{
while (stack[0]>1 && cross(a[stack[stack[0]-1]],a[stack[stack[0]]],C)<0)
use[stack[stack[0]--]]=false;
}
void convex_hull()
{
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;i++)
{
del(a[i]);
stack[++stack[0]]=i;
use[i]=true;
}
for (int i=n;i;i--)
{
if (use[i])
continue;
del(a[i]);
stack[++stack[0]]=i;
use[i]=true;
}
}
int main()
{
in>>n;
for (int i=1;i<=n;i++)
in>>a[i].x>>a[i].y;
convex_hull();
out<<stack[0]<<"\n";
for (int i=1;i<=stack[0];i++)
print(a[stack[i]]);
return 0;
}