Pagini recente » Cod sursa (job #133624) | Cod sursa (job #841192) | Cod sursa (job #1883514) | Cod sursa (job #2831340) | Cod sursa (job #2052289)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<float,float> Punct;
const int NMAX = 120005;
const double INF = 1e-12;
ifstream in("infasuratoare.in");ofstream out("infasuratoare.out");
int N;
Punct v[NMAX];
bool vis[NMAX];
int st[NMAX],varf;
void citire() {
in >> N;
for(int i = 1; i <= N; ++i) in >> v[i].x >> v[i].y;
}
double produs(Punct O, Punct A, Punct B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
void rezolvare() {
sort(v + 1,v + N + 1);
st[1] = 1; st[2] = 2; varf = 2;
vis[2] = 1;
for(int i = 1, p = 1; i > 0; i+= (p = (i == N ? -p :p))) {
if(vis[i]) continue;
while(varf >= 2 and produs(v[st[varf - 1]], v[st[varf]], v[i]) < INF)
vis[st[varf--]] = 0;
st[++varf] = i;
vis[i] = 1;
}
out << varf - 1 << '\n';
out << setprecision(6) << fixed;
for(int i = 1; i < varf; ++i) out << v[st[i]].x << " " << v[st[i]].y << '\n';
}
int main() {
citire();
rezolvare();
}