Pagini recente » Cod sursa (job #1118619) | Cod sursa (job #2642274) | Cod sursa (job #2362377) | Cod sursa (job #441587) | Cod sursa (job #1409494)
#include <bits/stdc++.h>
#define N 120005
#define punct pair<double, double>
#define x first
#define y second
using namespace std;
punct p[N], q[N];
int cnt, n, i, mini;
double cp(punct a, punct b, punct c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
bool crit(punct a, punct b)
{
return cp(p[1], a, b) < 0.0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
mini = 1;
for(i = 1; i <= n; i++)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
if(p[i] < p[mini])
mini = i;
}
swap(p[1], p[mini]);
sort(p + 2, p + n + 1, crit);
for(i = 1; i <= n; i++)
{
while(cnt > 1 && cp(q[cnt - 1], q[cnt], p[i]) > 0)cnt--;
q[++cnt] = p[i];
}
printf("%d\n", cnt);
for(; cnt; cnt--)
printf("%.12lf %.12lf\n", q[cnt].x, q[cnt].y);
return 0;
}