Pagini recente » Cod sursa (job #1996996) | Cod sursa (job #2657844) | Cod sursa (job #868821) | Cod sursa (job #3226035) | Cod sursa (job #2477652)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120010;
typedef pair<double, double> pdd;
const double eps = 1e-10;
vector<pdd> V(MAXN);
int N;
pdd firstPoint = {1e16, 1e16};
int firstPos = -1;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector<pdd> stk;
double cross(pdd a, pdd b, pdd c) {
return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}
int main() {
fin >> N;
V.resize(N);
for (int i = 0; i < N; i++) {
fin >> V[i].first >> V[i].second;
if (V[i] < firstPoint) {
firstPoint = V[i];
firstPos = i;
}
}
swap(V[0], V[firstPos]);
//cout << firstPoint.first << " " << firstPoint.second << endl;
sort(V.begin() + 1, V.end(), [](pdd a, pdd b) {
return cross(firstPoint, a, b) < 0;
});
//cout << endl;
//for (auto point : V) cout << point.first << " " << point.second << endl;
stk.push_back(firstPoint);
stk.push_back(V[1]);
for (int i = 2; i < V.size(); i++) {
pdd currPoint = V[i];
while ((cross(stk[stk.size() - 2], stk[stk.size() - 1], currPoint) >= 0) && stk.size() > 2) stk.pop_back();
stk.push_back(currPoint);
}
fout << stk.size() << endl;
reverse(stk.begin(), stk.end());
for (auto point: stk) fout << fixed << setprecision(6) << point.first << " " << point.second << "\n";
return 0;
}