Pagini recente » Cod sursa (job #1810806) | Cod sursa (job #1838196) | Cod sursa (job #2852021) | Cod sursa (job #1454090) | Cod sursa (job #2233852)
#include<bits/stdc++.h>
#define x first
#define y second
#define P pair<double, double>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n;
pair<double, double>v[120002], minn;
int poz;
double lol (P p, P a, P b) {
return (a.x - p.x) * (b.y - p.y) - (a.y - p.y) * (b.x - p.x);
}
bool cmp (P x, P y) {
return lol(v[1], x, y) < 0;
}
P st[120002];
int main()
{
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> v[i].x >> v[i].y;
}
poz = 1;
minn = v[1];
for (int i = 1; i <= n; i++) {
if (v[i] < minn) {
minn = v[i];
poz = i;
}
}
swap(v[1], v[poz]);
sort(v + 2, v + n + 1, cmp);
st[1] = v[1];
st[2] = v[2];
int vf = 2;
for (int i = 3; i <= n; i++) {
while (vf >= 2 && lol(st[vf - 1], st[vf], v[i]) > 0)
vf--;
st[++vf] = v[i];
}
fout << vf << "\n";
for (int i = vf; i >= 1; i--) {
fout << fixed << setprecision(6) << st[i].x << " " << st[i].y << "\n";
}
return 0;
}