Pagini recente » Cod sursa (job #1741754) | Profil tzutu | Cod sursa (job #1194099) | Cod sursa (job #352929) | Cod sursa (job #1691622)
#include <cstdio>
#include <algorithm>
using namespace std;
const int NM=120005;
struct Point{double x,y;};
int n,i,st[NM],nr,add;
Point a[NM];
bool ok[NM];
double X,Y;
bool semn(Point a, Point b, Point c)
{
double d= a.x*b.y+ b.x*c.y+ c.x*a.y;
d-=a.x*c.y+ b.x*a.y+ c.x*b.y;
return (d<=0);
}
bool cmp(Point a, Point b)
{
if(a.x==b.x) return (a.y<b.y);
return (a.x<b.x);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(i=1; i<=n; ++i) scanf("%lf%lf", &a[i].x, &a[i].y);
sort(a+1, a+n+1, cmp);
st[1]=1;st[2]=2;
nr=2; ok[2]=1;
for(i=3, add=1; !ok[1]; i+=add)
{
if(i==n) add=-1;
if(ok[i]) continue;
while(nr>=2 && semn(a[st[nr]], a[st[nr-1]], a[i])) ok[st[nr--]]=0;
ok[i]=1;
st[++nr]=i;
}
--nr;
printf("%d\n", nr);
for(i=nr; i; --i)
{
X=a[st[i]].x, Y=a[st[i]].y;
printf("%lf %lf\n", X,Y);
}
return 0;
}