Pagini recente » Cod sursa (job #59641) | Cod sursa (job #1436533) | Cod sursa (job #1289423) | Cod sursa (job #1428026) | Cod sursa (job #2176289)
#include <bits/stdc++.h>
using namespace std;
struct vec2
{
double x, y;
} v[120005];
int st[120005];
double det(const vec2& a, const vec2& b, const vec2& c)
{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp(const vec2& a, const vec2& b)
{
return det(v[1], a, b) > 0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n, pmin = 1;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%lf%lf", &v[i].x, &v[i].y);
if(v[pmin].y > v[i].y || (v[pmin].y == v[i].y && v[pmin].x > v[i].x))
pmin = i;
}
swap(v[1], v[pmin]);
sort(v + 2, v + 1 + n, cmp);
st[1] = 1;
st[2] = 2;
int lst = 2;
for(int i = 3; i <= n; i++)
{
while(lst >= 2 && det(v[st[lst - 1]], v[st[lst]], v[i]) <= 0)
lst--;
st[++lst] = i;
}
printf("%d\n", lst);
for(int i = 1; i <= lst; i++)
printf("%f %f\n", v[st[i]].x, v[st[i]].y);
return 0;
}