Pagini recente » Cod sursa (job #2152416) | Cod sursa (job #580282) | Cod sursa (job #2282027) | Cod sursa (job #87521) | Cod sursa (job #1500671)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 120005;
struct point {double x, y;} v[nmax];
inline double sarrus(point a, point b, point c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
inline 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);
int n, i, top=0, st[nmax], p=1;
bool viz[nmax];
scanf("%d", &n);
for(i=1; i<=n; i++)
{
scanf("%lf %lf", &v[i].x, &v[i].y);
viz[i]=false;
}
sort(v+1, v+n+1, cmp);
st[++top]=1, st[++top]=2, viz[2]=true;
for(i=1; i; i=i+p)
{
if (viz[i]==false)
{
while(top > 1 && sarrus(v[st[top-1]], v[st[top]], v[i])>=0)
viz[st[top--]]=false;
st[++top]=i;
viz[i]=true;
}
if(i==n) p=-p;
}
printf("%d\n", --top);
while(top)
{
printf("%.6lf %.6lf\n", v[st[top]].x, v[st[top]].y);
top--;
}
fclose(stdin);
fclose(stdout);
return 0;
}