Pagini recente » Cod sursa (job #2807835) | Cod sursa (job #1540535) | Cod sursa (job #4534) | Cod sursa (job #1556299) | Cod sursa (job #3219561)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMAX=120005;
int n,head;
struct Point
{
double x,y;
friend bool operator<(Point A,Point B)
{
if(A.x<B.x)
return 1;
if(A.x==B.x && A.y<B.y)
return 1;
return 0;
}
}points[NMAX],st[NMAX];
double cross_product(Point O,Point A,Point B)
{
return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
}
bool cmp(Point A,Point B)
{
return cross_product(points[1],A,B)<0;
}
void sort_points()
{
int pos=1;
for(int i=2; i<=n; i++)
if(points[i]<points[pos])
pos=i;
swap(points[1],points[pos]);
sort(points+2,points+n+1,cmp);
}
void convex_hull()
{
sort_points();
st[1]=points[1];
st[2]=points[2];
head=2;
for(int i=3;i<=n;i++)
{
while(head>=2 && cross_product(st[head-1],st[head],points[i])>0)
head--;
st[++head]=points[i];
}
}
int main()
{
f>>n;
for(int i=1; i<=n; i++)
f>>points[i].x>>points[i].y;
convex_hull();
g<<head<<'\n';
for(int i=head; i>=1; i--)
g<<setprecision(6)<<fixed<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}