Pagini recente » Cod sursa (job #231126) | Cod sursa (job #1749595) | Cod sursa (job #872056) | Rating cont de incercari (Radu_Petru) | Cod sursa (job #2502912)
#include <fstream>
#include <algorithm>
#include <iostream>
#include <stack>
#include <iomanip>
using namespace std;
struct punct {
double x, y;
int poz;
} v[240005];
bool viz[120005];
inline bool cmp(punct A, punct B) {
if (A.x == B.x)return A.y < B.y;
else return A.x < B.x;
}
double Delta(punct A, punct B, punct C) {
return B.x * C.y + C.x * A.y + A.x * B.y - B.x * A.y - C.x * B.y - A.x * C.y;
}
stack<punct> S;
int N;
punct sol[120005];
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin >> N;
for (int i = 1; i <= N; i++) {
fin >> v[i].x >> v[i].y;
v[i].poz = i;
}
sort(v + 1, v + N + 1, cmp);
for (int i = N + 1; i < 2 * N; i++) {
v[i] = v[2 * N - i];
}
//for (int i = 1; i < 2 * N; i++)
// cout << v[i].x << " " << v[i].y << "\n";
S.push(v[1]);
S.push(v[2]);
viz[v[1].poz] = 0;
viz[v[2].poz] = 1;
for (int i = 3; i < 2 * N; i++) {
if (viz[v[i].poz] == 0) {
punct a = S.top();
viz[a.poz] = 0;
S.pop();
while (Delta(S.top(), a, v[i]) <= 0 && S.size() > 1) {
a = S.top();
viz[a.poz] = 0;
S.pop();
}
if (Delta(S.top(), a, v[i]) > 0) {
S.push(a);
S.push(v[i]);
viz[a.poz] = 1;
viz[v[i].poz] = 1;
} else {
viz[v[i].poz] = 1;
S.push(v[i]);
}
//cout << i << " * " << S.size() << "\n";
}
}
int ct = 0;
while (!S.empty()) {
ct++;
sol[ct] = S.top();
S.pop();
}
fout << ct-1 << "\n";
for (int i = ct; i >= 2; i--) {
fout << fixed << setprecision(6) << sol[i].x << " " << sol[i].y;
fout << "\n";
}
}