Pagini recente » Cod sursa (job #896771) | Cod sursa (job #1727738) | Cod sursa (job #873521) | Cod sursa (job #1618468) | Cod sursa (job #2209305)
#include <bits/stdc++.h>
#define X first
#define Y second
#define eps 1e-12
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
vector<pair<double, double>> pct;
int N, k, st[240003], selected[120003];
double x, y;
inline int cmp(double a, double b)
{
if (a + eps < b) return -1;
if (b + eps < a) return 1;
return 0;
}
inline int det(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
return cmp(a.X * b.Y + b.X * c.Y + c.X * a.Y - a.Y * b.X - b.Y * c.X - c.Y * a.X, 0.0);
}
int main()
{
f >> N;
for(int i = 1; i <= N; i++) {
f >> x >> y;
pct.emplace_back(x, y);
}
sort(pct.begin(), pct.end());
st[++k] = 0;
st[++k] = 1;
selected[1] = true;
int i = 2, pas = 1;
while(!selected[0]) {
while(selected[i]) {
if(i == N - 1) pas = -1;
i += pas;
}
while(k >= 2 && det(pct[st[k]], pct[st[k - 1]], pct[i]) == -1) {
selected[st[k]] = false;
k--;
}
st[++k] = i;
selected[i] = true;
}
g << k - 1 << "\n" << setprecision(6) << fixed;
for(int it = k - 1; it >= 1; it--) {
auto aux = pct[st[it]];
g << aux.X << " " << aux.Y << "\n";
}
return 0;
}