Pagini recente » Cod sursa (job #1621541) | Cod sursa (job #1904258) | Cod sursa (job #3170607) | Cod sursa (job #1594363) | Cod sursa (job #2817207)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 12e4;
int st[NMAX + 5];
struct Pct {
double x,y;
bool operator<(Pct a) {
if (a.x == x)
return a.y < y;
return a.x < x;
}
}v[NMAX + 5],aux;
double dif(Pct a, Pct b, Pct c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(Pct a, Pct b) {
return dif(v[0], a, b) < 0;
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,poz,cnt;
fin >> n >> v[0].x >> v[0].y;
poz = 0;
for (int i = 1;i < n;i++) {
fin >> v[i].x >> v[i].y;
if (v[i] < v[poz])
poz = i;
}
aux = v[0];
v[0] = v[poz];
v[poz] = aux;
sort(v + 1, v + n, cmp);
st[0] = 0;
st[1] = 1;
cnt = 2;
for (int i = 2;i < n;i++) {
while (cnt >= 2 && dif(v[st[cnt - 2]], v[st[cnt - 1]], v[i]) > 0)
cnt--;
st[cnt++] = i;
}
fout << cnt << '\n';
fout << fixed;
for (int i = cnt - 1;i >= 0;i--)
fout << setprecision(8) << v[st[i]].x << " " << v[st[i]].y << '\n';
return 0;
}