Pagini recente » Cod sursa (job #1946796) | Cod sursa (job #481904) | Cod sursa (job #768669) | Cod sursa (job #3231261) | Cod sursa (job #2502894)
#include <fstream>
#include <algorithm>
#include <iostream>
#include <stack>
#include <iomanip>
using namespace std;
struct punct {
double x, y;
} v[240005];
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;
}
sort(v + 1, v + N + 1, cmp);
for (int i = N + 1; i < 2 * N; i++) {
v[i] = v[2 * N - i];
}
S.push(v[1]);
S.push(v[2]);
for (int i = 3; i < 2 * N; i++) {
punct a = S.top();
S.pop();
while (Delta(S.top(), a, v[i]) <= 0 && S.size() > 1) {
a = S.top();
S.pop();
}
if (Delta(S.top(), a, v[i]) >= 0) {
S.push(a);
S.push(v[i]);
} else S.push(v[i]);
}
int ct=0;
while (!S.empty()) {
ct++;
sol[ct]=S.top();
S.pop();
}
fout<<ct<<"\n";
for(int i=ct;i>=1;i--)
{
fout<<fixed<<setprecision(6)<<sol[i].x<<" "<<sol[i].y;
fout<<"\n";
}
}