Pagini recente » Cod sursa (job #803122) | Cod sursa (job #920798) | Cod sursa (job #2415902) | Cod sursa (job #703207) | Cod sursa (job #1802957)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int N = 120010, MAX = 1000000010;
int n, m, i, j, k, st[N], ind;
struct punct{
double x, y;
} a[N], x, aux;
double afla(punct a, punct b, punct c){
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp(punct a, punct b) {
double p1 = b.x * a.y;
double p2 = a.x * b.y;
if (p1 < p2) {
return 1;
}
return 0;
}
int main() {
x.x = MAX;
x.y = MAX;
fin >> n;
for (i = 1; i <= n; ++i) {
fin >> a[i].x >> a[i].y;
if (a[i].y < x.y || (a[i].y == x.y && a[i].x < x.x))
x = a[i], ind = i;
}
aux = a[ind];
a[ind] = a[1];
a[1] = aux;
for (i = 1; i <= n; ++i) {
a[i].x -= x.x, a[i].y -= x.y;
}
sort(a + 2, a + n + 1, cmp);
st[1] = 1;
st[2] = 2;
k = 2;
for (i = 3; i <= n; ++i) {
while(k >= 2 && afla(a[st[k - 1]], a[st[k]], a[i]) < 0) {
k--;
}
st[++k] = i;
}
fout << k << "\n" << fixed;
for (i = 1; i <= k; ++i) {
fout << setprecision(6) << a[st[i]].x + x.x << ' ' << a[st[i]].y + x.y << "\n";
}
return 0;
}