Pagini recente » Cod sursa (job #2844054) | Cod sursa (job #2869936) | Cod sursa (job #2847446) | Cod sursa (job #1829659) | Cod sursa (job #1222376)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 120010
#define EPS 1e-10
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct {
long double X, Y;
Punct() {
X = Y = 0;
}
Punct(long double X, long double Y) {
this->X = X;
this->Y = Y;
}
} S[MAX];
vector<Punct> Sup, Sinf;
int N;
bool cmp(Punct A, Punct B) {
if(abs(A.X-B.X) < EPS) return A.Y < B.Y;
return A.X < B.X;
}
long double Det(Punct A, Punct B, Punct C) {
return A.X*B.Y + B.X*C.Y + C.X*A.Y - B.X*A.Y - C.X*B.Y - A.X*C.Y;
}
void Subsets() {
Sup.push_back(S[1]);
Sinf.push_back(S[1]);
for (int i = 2; i < N; i++) {
if (Det(S[1], S[N], S[i]) > EPS) {
Sup.push_back(S[i]);
} else {
Sinf.push_back(S[i]);
}
}
Sup.push_back(S[N]);
Sinf.push_back(S[N]);
}
void UpSubset() {
int k = 1;
for (int i = 2; i < Sup.size(); i++) {
while (k >= 1 && Det(Sup[k-1], Sup[i], Sup[k]) < EPS) k--;
Sup[++k] = Sup[i];
}
Sup.resize(k+1);
}
void InfSubset() {
int k = 1;
for (int i = 2; i < Sinf.size(); i++) {
while (k >= 1 && Det(Sinf[k-1], Sinf[i], Sinf[k]) > EPS) k--;
Sinf[++k] = Sinf[i];
}
Sinf.resize(k+1);
}
int main() {
f >> N;
for (int i = 1; i <= N; i++) {
f >> S[i].X >> S[i].Y;
}
sort(S+1, S+N+1, cmp);
Subsets();
UpSubset();
InfSubset();
g << setprecision(13) << fixed;
g << Sup.size() + Sinf.size() - 2 << "\n";
for (int i = Sup.size() - 1; i >= 0; i--) {
g << Sup[i].X << " " << Sup[i].Y << "\n";
}
for (int i = 1; i < Sinf.size() - 1; i++) {
g << Sinf[i].X << " " << Sinf[i].Y << "\n";
}
return 0;
}