Pagini recente » Cod sursa (job #1415343) | Cod sursa (job #167518) | Cod sursa (job #1244619) | Cod sursa (job #777570) | Cod sursa (job #1073240)
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef pair <double, double> punct;
typedef vector <punct> poligon;
const int N = 12e5 + 5;
poligon P;
punct S[N];
int n, k;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
inline double cross(punct A, punct B, punct C) {
return (B.first - A.first) * (C.second - A.second) - (C.first - A.first) * (B.second - A.second);
}
inline bool cmp (punct A, punct B) {
return cross(P[0], A, B) < 0;
}
int main() {
fin >> n;
int pos = 0;
for (int i = 0; i < n; ++i) {
punct p;
fin >> p.first >> p.second;
P.push_back(p);
if (P[pos] > P[i])
pos = i;
}
swap (P[pos], P[0]);
sort(P.begin()+1, P.end(), cmp);
S[k++] = P[0];
S[k++] = P[1];
for (int i = 2; i < n; ++i) {
while (k > 1 && cross (S[k-2], S[k-1], P[i]) > 0)
--k;
S[k++] = P[i];
}
fout << fixed <<k << "\n";
for (int i = k-1; i >= 0; --i)
fout << setprecision(9) << S[i].first << " " << S[i].second << "\n";
fout.close();
return 0;
}