Pagini recente » Cod sursa (job #1497237) | Cod sursa (job #2841098) | Cod sursa (job #302534) | Cod sursa (job #2076310) | Cod sursa (job #1916968)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120005;
int n;
pair < double, double > points[NMAX];
int head;
pair < double, double > st[NMAX];
void read() {
fin >> n;
for (int i = 0; i < n; ++ i)
fin >> points[i].first >> points[i].second;
}
inline double crossProduct(const pair < double, double >& A, const pair < double, double >& B, const pair < double, double >& C) {
return (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
}
inline bool cmp(const pair < double, double >& A, const pair < double, double >& B) {
return crossProduct(points[0], A, B) < 0;
}
void sortPoints() {
int pos = 0;
for (int i = 1; i < n; ++ i)
if (points[i] < points[pos])
pos = i;
swap(points[0], points[pos]);
sort(points + 1, points + n, cmp);
}
void convexHull() {
sortPoints();
st[head ++] = points[0];
st[head ++] = points[1];
for (int i = 2; i < n; ++ i) {
while (head >= 2 && crossProduct(st[head - 2], st[head - 1], points[i]) > 0)
-- head;
st[head ++] = points[i];
}
}
void print() {
fout << head << "\n";
for (int i = head - 1; i >= 0; -- i)
fout << fixed << setprecision(12) << st[i].first << " " << st[i].second << "\n";
}
int main()
{
read();
fin.close();
convexHull();
print();
fout.close();
return 0;
}