Pagini recente » Cod sursa (job #2220121) | Cod sursa (job #2235608) | Cod sursa (job #540884) | Cod sursa (job #2224834) | Cod sursa (job #3325911)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct {
long double x, y;
} pct[120002];
int n, i, mi, top, stiv[120002];
Punct rasp[120002];
static inline long double Det(Punct p1, Punct p2, Punct p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
static inline bool Cmp(Punct a, Punct b) {
return Det(pct[1], a, b) > 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
fin >> n;
mi = 1;
for(i = 1; i <= n; i++) {
fin >> pct[i].x >> pct[i].y;
if(pct[i].y < pct[mi].y || (pct[i].y == pct[mi].y && pct[i].x < pct[mi].x)) {
mi = i;
}
}
swap(pct[1], pct[mi]);
sort(pct + 2, pct + n + 1, Cmp);
for(i = 1; i <= n; i++) {
while(top >= 2 && Det(pct[stiv[top - 1]], pct[stiv[top]], pct[i]) < 0) top--;
stiv[++top] = i;
}
fout << top << "\n";
for(i = 1; i <= top; i++) fout << setprecision(12) << fixed << pct[stiv[i]].x << " " << pct[stiv[i]].y << "\n";
return 0;
}