Pagini recente » Cod sursa (job #1750264) | Cod sursa (job #166598) | Cod sursa (job #702806) | jc2020/clasament | Cod sursa (job #2971328)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#endif
#define endl '\n'
const int NMAX = 120005;
struct Point {
double x, y;
bool operator==(const Point &p) {
return x == p.x && y == p.y;
}
bool operator<(const Point &p) {
if (x == p.x) return y < p.y;
return x < p.x;
}
};
int n;
Point a[NMAX];
vector<int> st;
inline double det(const Point &a, const Point &b, const Point &c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
// return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}
void read() {
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> a[i].x >> a[i].y;
}
}
bool cmp(const Point &p1, const Point &p2) {
return det(a[1], p1, p2) < 0;
}
void precalc() {
int pos = 1;
for (int i = 2; i <= n; i++) {
if (a[i] < a[pos]) {
pos = i;
}
}
swap(a[1], a[pos]);
sort(a + 2, a + n + 1, cmp);
}
void solve() {
st = {1, 2};
for (int i = 3; i <= n; i++) {
if (a[st.back()] == a[i]) continue;
while (st.size() > 1 && det(a[st[st.size() - 2]], a[st.back()], a[i]) > 0) {
st.pop_back();
}
st.push_back(i);
}
fout << st.size() << endl;
for (int i = st.size() - 1; i >= 0; i--) {
fout << setprecision(6) << fixed << a[st[i]].x << ' ' << a[st[i]].y << endl;
}
}
int main() {
read();
precalc();
solve();
return 0;
}