Pagini recente » Cod sursa (job #2956962) | Cod sursa (job #731255) | Cod sursa (job #663030) | Cod sursa (job #2971636) | Cod sursa (job #995431)
Cod sursa(job #995431)
#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 120010
int n, k, a, b, st0, nd;
int st[maxn];
struct punct
{
double x, y;
};
punct p[maxn];
inline int cmp(const punct &a, const punct &b)
{
return (a.x-p[1].x)*(b.y-p[1].y)<(b.x-p[1].x)*(a.y-p[1].y);
}
inline int semn(const punct &a, const punct &b, const punct &c)
{
double val = a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y;
if(val>0)
return 1;
if(val<0)
return -1;
return 0;
}
void infasuratoare()
{
for(int i=1; i<=nd; ++i)
if(p[i].x<p[1].x || (p[i].x==p[1].x && p[i].y<p[1].y))
swap(p[i], p[1]);
sort(p+2, p+nd+1, cmp);
for(int i=1; i<=nd; ++i)
{
if(st0>=2)
while(st0>=2 && semn(p[st[st0-1]], p[st[st0]], p[i])>0)
--st0;
st[++st0]=i;
}
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &nd);
for(int i=1; i<=nd; ++i)
scanf("%lf%lf", &p[i].x, &p[i].y);
infasuratoare();
printf("%d\n", st0);
for(int i=st0; i; --i)
printf("%.6lf %.6lf\n", p[st[i]].x, p[st[i]].y);
return 0;
}