Pagini recente » Cod sursa (job #3163146) | Cod sursa (job #823307) | Cod sursa (job #1695126) | Cod sursa (job #1164776) | Cod sursa (job #3197636)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAXN = 12e4;
pair<long double, long double> P[MAXN];
long double lmx, lmy;
int N, leftmost = -1;
int st[MAXN], k = 0;
long double det(pair<long double, long double> A, pair<long double, long double> B, pair<long double, long double> C)
{
long double x1, y1, x2, y2, x3, y3;
tie(x1, y1) = A;
tie(x2, y2) = B;
tie(x3, y3) = C;
return x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3;
}
int main()
{
fin >> N;
long double x, y;
for(int i = 0; i < N; ++i) {
fin >> x >> y;
P[i] = make_pair(x, y);
if(leftmost == -1 || x < lmx || x == lmx && y < lmy) {
lmx = x;
lmy = y;
leftmost = i;
}
}
swap(P[0], P[leftmost]);
sort(P + 1, P + N, [&](auto a, auto b) {
return det(P[0], a, b) >= 0;
});
st[k++] = 0;
st[k++] = 1;
for(int i = 2; i < N; ++i) {
while(k > 1 && det(P[st[k-2]], P[st[k-1]], P[i]) < 0)
--k;
st[k++] = i;
}
// trig order
/*sort(st + 1, st + k, [&](int a, int b) {
return det(P[0], P[a], P[b]) >= 0;
});*/
fout << k << '\n';
fout << fixed << setprecision(6);
for(int i = 0; i < k; ++i) {
tie(x, y) = P[st[i]];
fout << x << ' ' << y << '\n';
}
return 0;
}